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

Categories:

题目描述
思路分析
1. 解法一：双指针（首尾对撞）（推荐）
2. 解法二：快慢双指针
相似题目

题目描述

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

思路分析

解法一：双指针（首尾对撞）（推荐）

核心思路：

使用首尾两个指针，left 从左向右找偶数，right 从右向左找奇数。

当 left 指向偶数且 right 指向奇数时，交换两者，使奇数前移、偶数后移。

重复上述过程直到 left >= right，一次遍历即可完成分区。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，两个指针各自最多移动 n 次。

空间复杂度：O(1)，原地交换，不使用额外空间。

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            // left 向右找第一个偶数
            while (left < right && nums[left] % 2 != 0) {
                left++;
            }
            // right 向左找第一个奇数
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            // 将偶数与奇数交换，奇数前移、偶数后移
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }

        return nums;
    }
}

func exchange(nums []int) []int {
    left, right := 0, len(nums)-1

    for left < right {
        // left 向右找第一个偶数
        for left < right && nums[left]%2 != 0 {
            left++
        }
        // right 向左找第一个奇数
        for left < right && nums[right]%2 == 0 {
            right--
        }
        // 将偶数与奇数交换，奇数前移、偶数后移
        if left < right {
            nums[left], nums[right] = nums[right], nums[left]
        }
    }

    return nums
}

解法二：快慢双指针

核心思路：

使用快慢两个指针，slow 指向待填入奇数的位置，fast 向右遍历数组。

当 fast 遇到奇数时，将其与 slow 位置的元素交换，然后 slow 右移一位。

遍历结束后，[0, slow) 区间全为奇数，[slow, n) 区间全为偶数。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，fast 指针遍历整个数组一次。

空间复杂度：O(1)，原地交换，不使用额外空间。

class Solution {
    public int[] exchange(int[] nums) {
        // slow 指向下一个应放置奇数的位置
        int slow = 0;

        for (int fast = 0; fast < nums.length; fast++) {
            // fast 遇到奇数时，与 slow 位置交换
            if (nums[fast] % 2 != 0) {
                int tmp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = tmp;
                slow++;
            }
        }

        return nums;
    }
}

func exchange(nums []int) []int {
    // slow 指向下一个应放置奇数的位置
    slow := 0

    for fast := 0; fast < len(nums); fast++ {
        // fast 遇到奇数时，与 slow 位置交换
        if nums[fast]%2 != 0 {
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow++
        }
    }

    return nums
}

相似题目

题目	难度	考察点
75. 颜色分类	中等	双指针、三路划分
283. 移动零	简单	双指针、原地分区
27. 移除元素	简单	双指针、原地覆盖
905. 按奇偶排序数组	简单	双指针、奇偶分区
922. 按奇偶排序数组 II	简单	双指针、奇偶位置分配
86. 分隔链表	中等	双指针、链表分区
912. 排序数组	中等	双指针、快速排序分区

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/87028700