颜色分类

题目要求

给定一个数组 nums，它包含三种元素，分别用整数 0、1 和 2 表示，这些整数分别代表红色、白色和蓝色。数组中的元素总数为 n。要求编写一个算法，能够原地（不使用额外空间）对这个数组进行排序，使得排序后数组中相同颜色的元素相邻，并且按照红色、白色、蓝色的顺序排列。在这个问题中，你不能使用任何编程语言的库内置的排序函数。

解题思路

这个问题可以用三指针的方法来解决，通常被称为荷兰国旗问题，因为它涉及到三种颜色的排序，类似荷兰国旗的三色区分。以下是解题的步骤：

初始化三个指针：p0、p1和p2。其中p0指向数组的开始位置，p1指向数组的当前考察位置，p2指向数组的末尾。
遍历数组，移动p1指针：
- 如果nums[p1] == 0，说明是红色，应该放在数组的前面。将nums[p1]和nums[p0]交换，然后p0和p1都向前移动一位。
- 如果nums[p1] == 1，说明是白色，已经在正确的位置，只需要将p1向前移动一位。
- 如果nums[p1] == 2，说明是蓝色，应该放在数组的后面。将nums[p1]和nums[p2]交换，然后p2向后移动一位。这里不移动p1，因为交换后的nums[p1]可能是任何颜色，需要在下一次迭代中再次检查。
当p1超过p2时，遍历结束，此时数组已经按照红色、白色、蓝色的顺序排好。

这个算法的关键在于，p0的左侧都是红色（0），p2的右侧都是蓝色（2），而p1在遍历中将数组中的白色（1）留在中间。通过交换元素，我们可以确保每次迭代后，所有颜色都被放置到它们正确的位置上。这个过程不需要额外的数组空间，因此是原地排序。

Golang 版本

package main

import "fmt"

func sortColors(nums []int) {
    p0, p1 := 0, 0
    p2 := len(nums) - 1

    for p1 <= p2 {
        switch nums[p1] {
        case 0:
            nums[p0], nums[p1] = nums[p1], nums[p0]
            p0++
            p1++
        case 1:
            p1++
        case 2:
            nums[p1], nums[p2] = nums[p2], nums[p1]
            p2--
        }
    }
}

func main() {
    nums := []int{2, 0, 2, 1, 1, 0}
    sortColors(nums)
    fmt.Println(nums) // Output should be [0, 0, 1, 1, 2, 2]
}

这段代码实现了上述的三指针方法，用于原地排序一个包含红色（0）、白色（1）和蓝色（2）的数组。在 main 函数中，我们定义了一个示例数组，并调用 sortColors 函数来对其进行排序，最后打印出排序后的数组。

C++版本

#include <iostream>
#include <vector>

void sortColors(std::vector<int>& nums) {
    int p0 = 0, p1 = 0, p2 = nums.size() - 1;

    while (p1 <= p2) {
        if (nums[p1] == 0) {
            std::swap(nums[p0++], nums[p1++]);
        } else if (nums[p1] == 1) {
            p1++;
        } else if (nums[p1] == 2) {
            std::swap(nums[p1], nums[p2--]);
        }
    }
}

int main() {
    std::vector<int> nums = {2, 0, 2, 1, 1, 0};
    sortColors(nums);
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

这段 C++代码实现了与 Golang 版本相同的逻辑。它定义了一个 sortColors 函数，该函数接受一个整数类型的向量引用 nums，并使用三指针技术对其进行排序。在 main 函数中，我们创建了一个示例向量 nums，调用 sortColors 函数对其进行排序，并打印出排序后的结果。

Python 版本

def sort_colors(nums):
    p0, p1, p2 = 0, 0, len(nums) - 1

    while p1 <= p2:
        if nums[p1] == 0:
            nums[p0], nums[p1] = nums[p1], nums[p0]
            p0 += 1
            p1 += 1
        elif nums[p1] == 1:
            p1 += 1
        else:
            nums[p1], nums[p2] = nums[p2], nums[p1]
            p2 -= 1

if __name__ == "__main__":
    nums = [2, 0, 2, 1, 1, 0]
    sort_colors(nums)
    print(nums)  # Output should be [0, 0, 1, 1, 2, 2]

这段 Python 代码实现了前面描述的三指针方法，用于原地排序一个包含红色（0）、白色（1）和蓝色（2）的列表。在 if __name__ == "__main__": 块中，我们定义了一个示例列表 nums，调用 sort_colors 函数来对其进行排序，并打印出排序后的列表。

Java 版本

public class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, p1 = 0, p2 = nums.length - 1;

        while (p1 <= p2) {
            if (nums[p1] == 0) {
                int temp = nums[p0];
                nums[p0] = nums[p1];
                nums[p1] = temp;
                p0++;
                p1++;
            } else if (nums[p1] == 1) {
                p1++;
            } else {
                int temp = nums[p2];
                nums[p2] = nums[p1];
                nums[p1] = temp;
                p2--;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 0, 2, 1, 1, 0};
        solution.sortColors(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

这段 Java 代码实现了之前描述的三指针方法，用于原地排序一个包含红色（0）、白色（1）和蓝色（2）的数组。在 main 方法中，我们创建了一个示例数组 nums，调用 sortColors 方法来对其进行排序，并打印出排序后的数组。

Rust 版本

fn sort_colors(nums: &mut Vec<i32>) {
    let (mut p0, mut p1, mut p2) = (0, 0, nums.len() as i32 - 1);

    while p1 <= p2 {
        match nums[p1 as usize] {
            0 => {
                nums.swap(p0 as usize, p1 as usize);
                p0 += 1;
                p1 += 1;
            },
            1 => p1 += 1,
            2 => {
                nums.swap(p1 as usize, p2 as usize);
                p2 -= 1;
            },
            _ => (),
        }
    }
}

fn main() {
    let mut nums = vec![2, 0, 2, 1, 1, 0];
    sort_colors(&mut nums);
    println!("{:?}", nums); // Output should be [0, 0, 1, 1, 2, 2]
}

这段 Rust 代码实现了之前描述的三指针方法，用于原地排序一个包含红色（0）、白色（1）和蓝色（2）的向量。在 main 函数中，我们创建了一个示例向量 nums，调用 sort_colors 函数来对其进行排序，并打印出排序后的向量。

总结

上述解法采用了一个称为“三指针”的方法来解决颜色排序问题，这个问题也被称为荷兰国旗问题。这种方法的核心思想是将数组分为三个部分：

红色区域（0），由指针 p0 定界。
白色区域（1），在指针 p1 和 p2 之间。
蓝色区域（2），由指针 p2 定界。

算法的执行过程如下：

初始化三个指针：p0 和 p1 都设置为数组的起始位置，p2 设置为数组的末尾位置。
遍历数组，直到 p1 超过 p2。
根据 p1 指向的元素执行操作：
- 如果元素是 0，将其与 p0 指向的元素交换，并将 p0 和 p1 都向前移动一位。
- 如果元素是 1，只将 p1 向前移动一位。
- 如果元素是 2，将其与 p2 指向的元素交换，并将 p2 向后移动一位。
当 p1 超过 p2 时，所有的 0 都在数组的前面，所有的 2 都在数组的后面，而 1 自然就位于中间，从而完成排序。

这种方法的优点是它能够在一次遍历中完成排序，时间复杂度为 O(n)，并且不需要使用额外的存储空间，空间复杂度为 O(1)，即原地排序。这种方法适用于有限数量的唯一值需要排序的情况，特别是在这些值表示特定类别或颜色时。

hot-100