JZ81调整数组顺序使奇数位于偶数前面(二)

描述

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

方法1

思路：

既然要把所有的奇数放在数组前面，所有的偶数放在数组后面，那可以统计奇数在原数组中出现了多少次，这样就可以找到二者的分界线。有了分界线以后，前面就是奇数，后面就是偶数，可以利用两个指针分别指向二者的开头，遇到一个元素就添加到相应位置，然后指针移动。（该方法保证了相对位置不变）

代码

public int[] reOrderArrayTwo (int[] array) { // write code here if (array.length <= 0) return new int[0]; int[] result = new int[array.length]; int y = 0; for (int i = 0; i < array.length; i++) { if (array[i] % 2 == 1) y++; } int x = 0; for (int i = 0; i < array.length; i++) { if (array[i] % 2 == 1) { result[x] = array[i]; x++; } if (array[i] % 2 == 0) { result[y] = array[i]; y++; } } return result; }

方法2

思路

这道题不需要要求相对位置不变，因此我们可以采用位置交换的方法，只要奇数全部换到前面就可以了。利用左右双指针分别从数组首尾出发向中间走，交换其中的偶数在前奇数在后的情况。（该方法不能保证相对位置不变）

代码

package esay.JZ81调整数组顺序使奇数位于偶数前面2; import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param array int整型一维数组 * @return int整型一维数组 */ //方法1 /*public int[] reOrderArrayTwo (int[] array) { // write code here if (array.length <= 0) return new int[0]; int[] result = new int[array.length]; int y = 0; for (int i = 0; i < array.length; i++) { if (array[i] % 2 == 1) y++; } int x = 0; for (int i = 0; i < array.length; i++) { if (array[i] % 2 == 1) { result[x] = array[i]; x++; } if (array[i] % 2 == 0) { result[y] = array[i]; y++; } } return result; }*/ //方法2 public int[] reOrderArrayTwo(int[] array) { // write code here int i = 0; int j = array.length - 1; while (i < j) { //左边奇数，右边偶数 if (array[i] % 2 == 1 && array[j] % 2 == 0) { i++; j--; } //左右全是奇数 else if (array[i] % 2 == 1 && array[j] % 2 == 1) { i++; } //左边偶数，右边奇数 else if (array[i] % 2 == 0 && array[j] % 2 == 1) { int temp = array[j]; array[j] = array[i]; array[i] = temp; } //左右全是偶数 else { j--; } } return array; } public static void main(String[] args) { int[] arr = new int[]{1, 2, 3, 4}; System.out.println(Arrays.toString(new Solution().reOrderArrayTwo(arr))); } }