21 调整数组顺序使奇数位于偶数前面

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

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

解题思路：

可以仿照快速排序中 $partition$ 操作的思路，使用两个指针 $l$, $r$

• 当 $l$ 指向的是奇数时，$l$ 自增；

• 当 $r$ 指向的是偶数时，$r$ 自减；

• $l$ 和 $r$ 指向的元素交换。

循环上面的操作，直到 $l == r$ 。

代码：

public int[] exchange(int[] nums) {
    if (nums == null || nums.length == 0) {
        return new int[0];
    }
    int l = 0, r = nums.length - 1;
    while (l < r) {
        while (l < r && (nums[l] & 1) == 1) {
            l++;
        }
        while (l < r && (nums[r] & 1) == 0) {
            r--;
        }
        swap(nums, l, r);
    }
    return nums;
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

复杂度分析

• 时间复杂度$O(N)$：需要遍历 N 个元素。

• 空间复杂度$O(1)$：$l$ 和 $r$ 都是常数级的额外空间。