我正在尝试解决这个面试问题。我能够获得 O(N) 空间复杂度的 O(N) 解决方案。我想弄清楚是否有O(1) 空间的解决方案?
问题:
给定一个未排序的正数和负数数组。创建交替正数和负数的数组而不分别改变正数和负数的相对顺序。
输入:
输入的第一行包含一个整数 T,表示测试用例的数量。 每个测试用例的第一行是N,N是数组的大小。 每个测试用例的第二行包含 N 个输入 a[]。
输出:
打印一组交替的正数和负数。 注意:解决方案应以正数开头。
约束:
1≤T≤30 1≤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) 空间解决这个问题。
最佳答案
如果您不直接获取数组作为函数的输入,而是必须从标准输入流中读取数字,则意味着您必须创建数组 自己。问题还指出:
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));
}
}
关于algorithm - +ve 和 -ve nums 的拆分数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40593484/