该题原址:https://leetcode-cn.com/problems/sort-array-by-parity/
巧妙的方法需要对数组有深入的理解.
正确的思路是利用左右指针来判断数组两头的值是否为奇数或偶数,在进行相应操作后,移动左右指针,当左右指针相碰则遍历完成. 算法复杂度(O(N/2))
错误思路 : 将奇偶分别存放在一个数组中后,之后再按照先添加偶数数组,然后再把奇数数组添加进去返回该数组即可. 与上面的想法相比,效率太低了,不仅需要遍历整个数组,还需要在把两个数组的值在重新添加到一个新的数组! 算法复杂度(O(N))
1. 左右指针解法(摘自:https://leetcode-cn.com/crzzm/)
/** * 执行用时 : 3 ms, 在Sort Array By Parity的Java提交中击败了98.43% 的用户 *内存消耗 : 43.6 MB, 在Sort Array By Parity的Java提交中击败了78.03% 的用户 * */ public int[] sortArrayByParity1(int[] A) { int i = 0; int j = A.length - 1; int[] B = new int[A.length]; for (int x = 0; x < A.length; x++) { if (A[x] % 2 == 0) { B[i] = A[x]; i++; } else { B[j] = A[x]; j--; } } return B; }2. 双指针解法(摘自:https://leetcode-cn.com/kico/)
/** *执行用时 : 3 ms, 在Sort Array By Parity的Java提交中击败了98.43% 的用户 *内存消耗 : 37.6 MB, 在Sort Array By Parity的Java提交中击败了98.33% 的用户 */ public int[] sortArrayByParity(int[] A) { if(A == null || A.length == 1) return A; //左、右指针初始化 int left = 0; int right = A.length - 1; int tem; while(left < right){ //左指针对应奇数值，右指针对应偶数值，进行交换 if((A[left] & 1) == 1 && (A[right] & 1) == 0){ tem = A[left]; A[left] = A[right]; A[right] = tem; }else if((A[left] & 1) == 0){ //左指针对应的是偶数值，符合题意，继续向右移动 left++; } else if((A[right] & 1) == 1){ //右指针对应的是奇数值，符合题意，继续向左移动 right--; } } return A; }3.首先想出的笨方法(考虑到双指针了,但是从没实现过,感觉太难就没有深入思考直接用最菜的方法)
class Solution { /** * 执行用时 : 14 ms, 在Sort Array By Parity的Java提交中击败了53.24% 的用户 *内存消耗 : 40.2 MB, 在Sort Array By Parity的Java提交中击败了89.33% 的用户 */ public static int[] sortArrayByParity(int[] A) { if (A == null || A.length == 1) { return A; } StringBuilder evenNum = new StringBuilder(); StringBuilder oddNum = new StringBuilder(); int[] arr = new int[A.length]; for (int i : A) { if (i % 2 != 0) { oddNum.append(i); oddNum.append(","); } else { evenNum.append(i); evenNum.append(","); } } if (evenNum.length() == 0 || oddNum.length() == 0) { // 判断A数组中是否全为偶数或全为奇数 return A; } String[] strEven = evenNum.toString().split(","); String[] strOdd = oddNum.toString().split(","); for (int i = 0; i < arr.length; i++) { if (i < strEven.length) { arr[i] = Integer.valueOf(strEven[i]); // 先将strEven数组的各个元素转换为int类型添加到arr数组中 } if (i >= strEven.length) { arr[i] = Integer.valueOf(strOdd[i - strEven.length]); // 之后就把奇数添加到arr数组中 } } return arr; } }要想到所有解法,先考虑效率高的(一般不是很容易实现)如何去实现它,实在完成不了在退而求其次,考虑另一个解法如何完成.
