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]; } }
