题目:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
思路:要求位置不变,就不能进行一般意义的交换。
1、空间换时间,新建两个数组用来保存奇数和偶数;
2、时间换空间,获取到第一个奇数的位置,判断它是否等于当前正在排序的下标,是则不用挪动位置;否则进行挪动位置。从找到的奇数下标开始往前进行,array[i]=array[i-1];当i等于正在排序的前一个array[i]=temp;
源码:
1、
public void reOrderArray(int [] array) {
List listodd=new ArrayList();
List listeve=new ArrayList();
for(int i=0;i<array.length;i++) {
if(array[i]%2==0)
listeve.add(array[i]);
else
listodd.add(array[i]);
}
listeve.addAll(0, listodd);
for(int i=0;i<listeve.size();i++)
array[i]=(int) listeve.get(i);
}
2、
public static void reOrderArray(int [] array) {
for(int i=0;i<array.length;i++) {
int index=oddIndex(array,i);
if(index!=i&&index<array.length) {
int temp=array[i];
array[i]=array[index];
remove(array,i,temp,index);
for(int j=0;j<array.length;j++)
System.out.print(array[j]+" ");
System.out.println();
}
}
}
public static int oddIndex(int[] arr,int index) {
int i;
for( i=index;i<arr.length;i++) {
if(arr[i]%2!=0)
break;
}
return i;
}
public static void remove(int[] arr,int index,int temp,int oddindex) {
for(int i=oddindex;i>index;i--) {
if(i==index+1)
arr[i]=temp;
else
arr[i]=arr[i-1];
}
}
网友评论