牛客解题思路：调整数组顺序使奇数位于偶数前面
调整数组顺序使奇数位于偶数前面
思路：需要保证奇数和奇数，偶数和偶数之间的相对位置不变。比较容易想到的一种方法是， 新开一个数组，先统计原数组中奇数的个数oddCnt，然后把原数组的奇偶数分别从0索引和oddCnt开始摆放：
public void reOrderArray(int[] nums) {int oddCnt = 0;for (int x : nums)if (!isEven(x))oddCnt++;int[] copy = nums.clone();int i = 0, j = oddCnt;for (int num : copy) {if (num % 2 == 1)nums[i++] = num;elsenums[j++] = num;}
}
public boolean isEven(int x) {return x % 2 == 0;
}我们还可以采用冒泡排序的思想，每次都将当前偶数上浮到当前最右边。时间复杂度 O(N^2)，空间复杂度 O(1)，时间换空间。
public void reOrderArray(int[] nums) {int N = nums.length;for (int i = N - 1; i > 0; i--) {for (int j = 0; j < i; j++) {if (isEven(nums[j]) && !isEven(nums[j + 1])) {swap(nums, j, j + 1);}}}
}
public boolean isEven(int x) {return x % 2 == 0;
}
public void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;
}最开始我还写了一种错误的方法，采用的双指针，永远指向第一个奇数和偶数，然后将其交换位置：
public void reOrderArray(int [] array) {int i = 0;int j = 0;while(i<array.length && array[i]%2 == 1){i++;}while(j<array.length && array[j]%2 == 0){j++;}while(i<array.length && j<array.length){if(i<j){int temp = array[i];array[i] = array[j];array[j] = temp;i++;j++;while(i<array.length && array[i]%2 == 1){i++;}while(j<array.length && array[j]%2 == 0){j++;}}else{j++;while(j<array.length && array[j]%2 == 0){j++;}}}
}我测试了一下，是可以将奇偶数分别放在前面和后面的，但是无法保证原始顺序，例如输入[1,2,3,4,5,6,7]，实际输出[1,3,5,7,2,6,4]，正确输出应该[1,3,5,7,2,4,6]，因此这个答案是不对的。我分析了一下原因，原因是比如i,j交换之后，i可能又会移动到j之前交换过的位置，导致某个数被两次交换，而他第二次被交换的时候被当成了后面才出现的数，然而这个数可能很早就出现过了，这就导致了顺序的混乱。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！