剑指offer 13.代码的完整性调整数组顺序使奇数位于偶数前面

佚名 6年前 (2019-04-24) 随笔 1675人围观抢沙发百度已收录

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。本渣渣解题思路：遍历整个数组array，遇到偶数，添加到list1；遇到奇数，添加到list2；再先后把list1和list2中的数添加到array 代码实现如下：

import java.util.LinkedList;
public class Solution {
public void reOrderArray(int [] array) {
LinkedList<Integer> list1=new LinkedList<Integer>();
LinkedList<Integer> list2=new LinkedList<Integer>();
for (int i = 0; i < array.length; i++) {
if (array[i]%2==0) {
list2.add(array[i]);
}else if (array[i]%2!=0) {
list1.add(array[i]);
}
}

for (int i = 0; i < list1.size(); i++) {
array[i]=list1.get(i);
}
int length=list1.size();
int i=0;
for (Integer integer : list2) {
array[length]=list2.get(i);
length++;
i++;
}

}

}

牛客大神：
新开数组空间换时间的解法, a.遍历数组,如果是奇数从头部放入到原数组中,并记录指针
b.如果是偶数,放入到新数组中,并记录指针
c.将新数组的元素安顺序,从最后一个奇数后边插入到原数组中

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Solution { public void reOrderArray(int [] array) { if (array != null) { int[] even = new int[array.length]; int indexOdd = 0; int indexEven = 0; for (int num : array) { if ((num & 1) == 1) { array[indexOdd++] = num; } else { even[indexEven++] = num; } } for (int i = 0; i < indexEven; i++) { array[indexOdd + i] = even[i]; } } } }