Medium

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

**注意：**不能使用代码库中的排序函数来解决这道题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

**进阶：**你可以不使用代码库中的排序函数来解决这道题吗？你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路

这道题有两种经典解法：

方法一：计数排序（两次遍历）

  • 第一次遍历统计0、1、2的个数
  • 第二次遍历按统计结果重新填充数组
  • 时间复杂度O(n)，空间复杂度O(1)

方法二：荷兰国旗问题（一次遍历）【推荐】 这是经典的三路快排思想，使用三个指针：

  • left：指向下一个0应该放置的位置
  • right：指向下一个2应该放置的位置
  • curr：当前遍历位置

核心思路：

  • 遇到0：与left位置交换，left和curr都右移
  • 遇到1：curr直接右移（1已经在正确区域）
  • 遇到2：与right位置交换，right左移，curr不动（因为交换来的元素还需要判断）

这种方法只需要一次遍历，是最优解法。当curr > right时结束，此时所有元素都已正确分类。

代码实现

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, curr = 0;
        
        while (curr <= right) {
            if (nums[curr] == 0) {
                swap(nums[left], nums[curr]);
                left++;
                curr++;
            } else if (nums[curr] == 2) {
                swap(nums[curr], nums[right]);
                right--;
            } else {
                curr++;
            }
        }
    }
};

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left, right, curr = 0, len(nums) - 1, 0
        
        while curr <= right:
            if nums[curr] == 0:
                nums[left], nums[curr] = nums[curr], nums[left]
                left += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[right] = nums[right], nums[curr]
                right -= 1
            else:
                curr += 1

public class Solution {
    public void SortColors(int[] nums) {
        int left = 0, right = nums.Length - 1, curr = 0;
        
        while (curr <= right) {
            if (nums[curr] == 0) {
                int temp = nums[left];
                nums[left] = nums[curr];
                nums[curr] = temp;
                left++;
                curr++;
            } else if (nums[curr] == 2) {
                int temp = nums[curr];
                nums[curr] = nums[right];
                nums[right] = temp;
                right--;
            } else {
                curr++;
            }
        }
    }
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let left = 0, right = nums.length - 1, curr = 0;
    
    while (curr <= right) {
        if (nums[curr]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型荷兰国旗算法计数排序
时间复杂度O(n)O(n)
空间复杂度O(1)O(1)

说明： 荷兰国旗算法只需要一次遍历，在实际应用中效率更高，是推荐解法。

相关题目