剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目

1
2
3
4
5
6
7
8
9
10
11
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
 

提示：
0 <= nums.length <= 50000
0 <= nums[i] <= 10000

思路

典型的双指针，在快排中的选择基准值（比x小的放左边，比x大的放右边）排序就是用的这种思想

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private static class Solution {
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length == 1) {
            return nums;
        }
        // 奇数
        int oddNum = 0;
        // 偶数
        int evenNum = nums.length - 1;
        while (oddNum < evenNum) {
            // 不是奇数则停止
            while (oddNum < evenNum && (nums[oddNum] & 1) == 1) {
                oddNum++;
            }

            // 不是偶数则停止
            while (oddNum < evenNum && (nums[evenNum] & 1) == 0) {
                evenNum--;
            }
            int temp = nums[oddNum];
            nums[oddNum] = nums[evenNum];
            nums[evenNum] = temp;
        }

        return nums;
    }
}