leetcode75 Sort Colors-zh

# 75. 颜色分类 (opens new window)

# 题目描述

给定一个包含红色、白色和蓝色，一共 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]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

提示：

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

进阶：

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

# 解法

# Python3

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Java

class Solution {
    public void sortColors(int[] nums) {
        int i = -1, j = nums.length;
        int cur = 0;
        while (cur < j) {
            if (nums[cur] == 0) {
                swap(nums, cur++, ++i);
            } else if (nums[cur] == 1) {
                ++cur;
            } else {
                swap(nums, cur, --j);
            }
        }
    }

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# C++

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Go

func sortColors(nums []int) {
	i, j, cur := -1, len(nums), 0
	for cur < j {
		if nums[cur] == 0 {
			i++
			nums[cur], nums[i] = nums[i], nums[cur]
			cur++
		} else if nums[cur] == 1 {
			cur++
		} else {
			j--
			nums[cur], nums[j] = nums[j], nums[cur]
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# ...

编辑

#leetcode

上次更新: 2021/10/30, 12:58:38

← leetcode74 Search a 2D Matrix-zh leetcode76 Minimum Window Substring-zh→