【剑指offer】-调整数组顺序使奇数位于偶数前面-13/67
调整数组顺序使奇数位于偶数前面
http://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593
1. 题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
2. 题目分析
- 第一个做法：以时间换空间，复杂度O(n²)
1. 遍历数组array，利用num来记录当前奇数的个数 2. 当遍历到奇数时，利用交换的思想，将此时的奇数交换至array[num]的位置 3. 最终，得到最后的结果
- 第二个做法：以空间换时间，复杂度O(n)
1. 开辟一个新的数组a，定义num1(代表array数组中奇数的个数)，num2(代表a数组中偶数的个数) 2. 遍历数组array。如果是奇数，将其array[num1++]，如果是偶数，将其a[num2++] 3. 最后，将a数组中的偶数转移到array数组中
3. 题目代码
- 第一个做法：以时间换空间，复杂度O(n²)
public void reOrderArray(int[] array) {
int num = 0;
int j = 0;
int temp = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 1) {
j = i;
while (j > num) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
j--;
}
num++;
}
}
} - 第二个做法：以空间换时间，复杂度O(n)
public void reOrderArray(int [] array) {
int[] a = new int[100];
int num1 = 0;
int num2 = 0;
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 0){
a[num1++] = array[i];
}else{
array[num2++] = array[i];
}
}
for(int i = 0; i < num1; i++){
array[num2++] = a[i];
}
} 
