有一个长度为2N的数组,有N个奇数,N个偶数,这些数字的位置任意,请写一个算法,要求:将奇数放在奇数位,偶数放在偶数位,并且时间复杂度位O(n),空间复杂度为O(1)。数组下标以0开始,即可认为是奇数位。
要求用JAVA语言实现。
------解决方案--------------------
自己写了一个,不知道时间复杂度和空间复杂度是否符合要求
public class Test {
public static void main(String[] args) {
int n = 8;
int[] arr = new int[2 * n];
boolean[] bs = new boolean[2 * n];
Random ran = new Random();
for(int i = 0; i < n; i++) {
arr[i] = ran.nextInt(50) * 2 + 2;
}
for(int i = 2 * n - 1; i >= n; i--) {
arr[i] = ran.nextInt(50) * 2 + 1;
}
for(int i = 0, j = 2 * n; i < j; i++) {
int r = ran.nextInt(j);
if(i == r) {
continue;
}
arr[i] = arr[i] ^ arr[r];
arr[r] = arr[i] ^ arr[r];
arr[i] = arr[i] ^ arr[r];
}
for(int i = 0; i < n * 2; i++) {
System.out.format("%d, ", arr[i]);
}
System.out.print("\n----------------------------------------------------\n");
for(int i = 0, j = 2 * n; i < j; i++) {
if(i % 2 == 0) {
int k = i - 1;
while(++k < j - 1 && arr[k] % 2 != 0);
if(i != k) {
arr[i] = arr[i] ^ arr[k];
arr[k] = arr[i] ^ arr[k];
arr[i] = arr[i] ^ arr[k];
}
} else {
int k = i - 1;
while(++k < j - 1 && arr[k] % 2 == 0);
if(i != k) {
arr[i] = arr[i] ^ arr[k];
arr[k] = arr[i] ^ arr[k];
arr[i] = arr[i] ^ arr[k];
}
}
}
for(int i = 0; i < n * 2; i++) {
System.out.format("%d, ", arr[i]);
}
}
}
------解决方案--------------------
int[] arr = {1,3,4,6,8,3};
int [] temp = new int[arr.length];
int oddIndex=1;//奇数的index
int evenIndex=0;//偶数的index
for(int num:arr){
if(num%2==1){
temp[oddIndex]=num;
oddIndex +=2;
}else{
temp[evenIndex]=num;
evenIndex +=2;
}
}
for(int num:temp){
System