Create 75. 颜色分类.md

CompetitiveLin · CompetitiveLin · commit 9737c46f202d · 2023-09-15T17:47:18.000+08:00
diff --git a/Two Pointers/75. 颜色分类.md b/Two Pointers/75. 颜色分类.md
@@ -0,0 +1,68 @@
+#### 75. 颜色分类
+
+难度：中等
+
+---
+
+给定一个包含红色、白色和蓝色、共 `n` 个元素的数组 `nums` ， **[原地](https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)** 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
+
+我们使用整数 `0`、 `1` 和 `2` 分别表示红色、白色和蓝色。
+
+必须在不使用库内置的 sort 函数的情况下解决这个问题。
+
+ **示例 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`
+
+ **进阶：** 
+
+*   你能想出一个仅使用常数空间的一趟扫描算法吗？
+
+---
+
+双指针：
+
+**尾指针**指向最后，**头指针**指向最前。另外需要一个**遍历指针**从头向尾遍历，然后分类讨论（重要）：
+
+1. 如果当前元素为 `0`，与头指针元素交换并将遍历指针和头指针都向右移动一个单位。
+2. 如果当前元素为 `1`，只移动遍历指针
+3. 如果当前元素为 `2`，与尾指针元素交换并左移尾指针，此时不移动遍历指针！！！
+
+```Java
+class Solution {
+    public void sortColors(int[] nums) {
+        int left = 0, right = nums.length - 1, index = 0;
+        while(index <= right){
+            if(nums[index] == 2){
+                swap(nums, index, right--);
+                continue;
+            } else if(nums[index] == 0){
+                swap(nums, left++, index);
+            }
+            index++;
+        }
+    }
+
+    private void swap(int[] nums, int left, int right){
+        int temp = nums[left];
+        nums[left] = nums[right];
+        nums[right] = temp;
+    }
+}
+```
