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

Lin2J
2021-07-21 / 0 评论 / 92 阅读
温馨提示:
本文最后更新于2021-07-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$ 都是常数级的额外空间。