【leetcode】精选 75. 颜色分类

待我称王封你为后i 2022-08-31 02:15 145阅读 0赞

### 精选 75. 颜色分类 ###

*  题目难度：中等
 *  双指针

> 链接：[https://leetcode-cn.com/problems/sort-colors/][https_leetcode-cn.com_problems_sort-colors]  
> 来源：力扣（LeetCode）

# 题目难度：中等 #

给定一个包含红色、白色和蓝色，一共 `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
    
    你可以不使用代码库中的排序函数来解决这道题吗？
    你能想出一个仅使用常数空间的一趟扫描算法吗？

模板

class Solution {
        
        public void sortColors(int[] nums) {
        
    
        }
    }

class Solution:
        def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """

# 双指针 #

我们也可以考虑使用指针 `r` 来交换 `0`，`l` 来交换 `2`。此时，`r` 的初始值为 `0`，而 `l` 的初始值为 `nums.lenght - 1`。在遍历的过程中，我们需要找出所有的 `0` 交换至数组的头部，并且找出所有的 `2` 交换至数组的尾部。

由于右指针 `r` 是从右向左移动的，因此当我们在从左向右遍历整个数组时，如果遍历到的位置超过了 `r` ，那么就可以直接停止遍历了。

初始化变量`p = 0`用于变量整个数组

*  使用两个指针 左`l = 0` 和 右`r = nums.lenght - 1`，指向数组的两端，分别用于`0`和`2`的交换

开始遍历整个数组

*  若遇到`0`，则跟`l`指针对应的值交换，即将它与`nums[l]`交换，然后`l++`向后移一位，`p也++`继续向后遍历；
 *  若遇到`1`，什么都不用做，`p++`继续向后遍历
 *  若遇到`2`，则跟`r`指针对应的值交换，即将它与`nums[r]`交换，然后`r--`向前移一位，此时需注意：交换后是否有可能将`2`交换出去？是的，完全有可能

什么时候会将`2`交换出去？怎么做？

*  当`p`和`r`的位置的值都是`2`时，交换完后相当于没变，所以还要继续对`p`指针的值进行判断，即`p`不动，`r--`向前移一位，直到`p`位置的值不是`2`为止

class Solution {
        
        public void sortColors(int[] nums) {
        
            int l = 0; // 初始化左指针，用于交换0
            int r = nums.length - 1; // 初始化右指针，用于交换2
    
    		int p = 0; 
    		// 当p > r 就结束循环
            while(p <= r){
        
                int v = nums[p]; //获取每个遍历的值
                if (v == 0){
        
                	// 与l指针位置的值交换，并且p和l向后移一位
                    swap(nums, p++, l++);
                } else if (v == 1){
        
                	// 什么都不用做，向后遍历
                    p++;
                } else {
         // v == 2
                	// 与2指针位置的值交换，只需r向前移一位，p不用动，还要继续判断
                    swap(nums, p, r--);
                }
            }
    
        }
    
        private void swap(int[] nums, int i, int j){
        
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l, r = 0, len(nums) - 1
        p = 0
        while p <= r:
            v = nums[p]
            if v == 0:
                nums[l], nums[p] = nums[p], nums[l]
                l += 1
                p += 1
            elif v == 1:
                p += 1
            else:
                nums[r], nums[p] = nums[p], nums[r]
                r -= 1

[https_leetcode-cn.com_problems_sort-colors]: https://leetcode-cn.com/problems/sort-colors/