algorithm - +ve 和 -ve nums 的拆分数组

Question

我正在尝试解决这个面试问题。我能够获得 O(N) 空间复杂度的 O(N) 解决方案。我想弄清楚是否有O(1) 空间的解决方案？

问题:

给定一个未排序的正数和负数数组。创建交替正数和负数的数组而不分别改变正数和负数的相对顺序。

输入:

输入的第一行包含一个整数 T，表示测试用例的数量。每个测试用例的第一行是N，N是数组的大小。每个测试用例的第二行包含 N 个输入 a[]。

输出:

打印一组交替的正数和负数。注意:解决方案应以正数开头。

约束:

1≤T≤301≤N≤100-1000 ≤ a[] ≤ 1000

示例:

输入

1
9
9 4 -2 -1 5 0 -5 -3 2

输出

9 -2 4 -1 5 -5 0 -3 2

.

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
    public static void main (String[] args) {
        //code
        Scanner sn = new Scanner(System.in);
        int T = sn.nextInt();
        for(int i=0; i<T; i++){
            int N = sn.nextInt();
            ArrayList<Integer> arr = new ArrayList<Integer>();
            ArrayList<Integer> pv_arr = new ArrayList<Integer>();
            ArrayList<Integer> ne_arr = new ArrayList<Integer>();
            for(int j=0; j<N; j++){
                int num = sn.nextInt();
                if(num<0){
                    ne_arr.add(num);
                }else{
                    pv_arr.add(num);
                }
            }

            int maxLen = Math.max(pv_arr.size(), ne_arr.size());
            for(int k = 0; k < maxLen; k++){
              if(k < pv_arr.size()){
                 System.out.print(pv_arr.get(k) + " ");
              }
              if(k < ne_arr.size()){
                 System.out.print(ne_arr.get(k) + " ");
              }
            }
            System.out.println(" ");
        }
    }
}

我的答案创建了两个数组 positive 和 negative 并交替打印它们。我尝试使用两个指针(一个正值和一个负值)我不确定如何用 O(N) 和 O(1) 空间解决这个问题。

Answer 1

如果您不直接获取数组作为函数的输入，而是必须从标准输入流中读取数字，则意味着您必须创建数组 自己。问题还指出:

The first line... The second line...

暗示输入是逐行提供给您的，而不是作为函数的参数。

这意味着就空间而言，最佳解决方案是 O(n)。您已经找到了一个可行的解决方案，但您仍然可以像您自己所说的那样使用“指针”方法来简化它:

public static void main (String[] args) {
    Scanner sn = new Scanner(System.in);
    int T = sn.nextInt();
    for(int i=0; i<T; i++){
        int N = sn.nextInt();
        int[] numbers = new int[N];
        int neg_ind = 1;
        int pos_ind = 0;

        for(int j=0; j<N; j++){
            int num = sn.nextInt();
            if(num < 0){
                numbers[neg_ind] = num;
                neg_ind += 2;
            }else{
                numbers[pos_ind] = num;
                pos_ind += 2;
            }
        }

        System.out.println(Arrays.toString(numbers));
    }
}