思路及解答两次遍历

第一次遍历收集奇数第二次遍历收集偶数这种方法虽然简单易懂但需要额外空间不符合题目要求javapublic class Solution { public int[] reorderArray(int[] nums) { if (nums null || nums.length 0) { return new int[0]; } int[] result new int[nums.length]; int index 0; // 第一次遍历收集所有奇数 for (int num : nums) { if (num % 2 1) { result[index] num; } } // 第二次遍历收集所有偶数 for (int num : nums) { if (num % 2 0) { result[index] num; } } return result; } }时间复杂度O(n)空间复杂度O(n)双指针交换推荐这道题需要奇数在⼀半偶数在另外⼀半就可以并没有要求他们之间的顺序那么就可以⽤双指针⼀个指针在左边⼀个指针在右边⽐如 1,3,5,6,7 :左指针往右遍历直到找到偶数也就是 6 停下来右指针往左⾛直到找到第⼀个奇数也就是 7 停下来。两者交换:左指针继续往右边⾛两个指针相遇结束这个时候其实偶数已经全部在右边了。这个例⼦⾥⾯只经过⼀次交换如果是多次交换那么结束的条件同样也是两个指针相遇。javapublic class Solution { public int[] reorderArray(int[] nums) { if (nums null || nums.length 1) { return nums; } int left 0; // 左指针从数组开头开始 int right nums.length - 1; // 右指针从数组末尾开始 while (left right) { // 左指针向右移动直到找到偶数 while (left right nums[left] % 2 1) { left; } // 右指针向左移动直到找到奇数 while (left right nums[right] % 2 0) { right--; } // 如果左指针仍在右指针左边交换奇偶数 if (left right) { int temp nums[left]; nums[left] nums[right]; nums[right] temp; left; right--; } } return nums;