75.颜色分类，双指针

linwt · linwt · commit ca50c3ec6a6f · 2022-04-16T17:12:21.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -33,6 +33,7 @@
 69. x 的平方根
 70. 爬楼梯
 72. 编辑距离
+75. 颜色分类
 76. 最小覆盖子串
 77. 组合
 78. 子集
diff --git a/leetcode_Java/DoneType.txt b/leetcode_Java/DoneType.txt
@@ -145,6 +145,7 @@
 41. 缺失的第一个正数
 54. 螺旋矩阵
 56. 合并区间
+75. 颜色分类
 88. 合并两个有序数组
 136. 只出现一次的数字
 169. 多数元素
diff --git a/leetcode_Java/Solution0075.java b/leetcode_Java/Solution0075.java
@@ -0,0 +1,60 @@
+// 75. 颜色分类
+
+
+/*
+单指针：两次遍历，第一次把0交换到前面，第二次把1交换到前面
+ */
+class Solution {
+    public void sortColors(int[] nums) {
+        int index = 0, n = nums.length;
+        for (int i = 0; i < n; i++) {
+            if (nums[i] == 0) {
+                swap(nums, i, index);
+                index++;
+            }
+        }
+        for (int i = index; i < n; i++) {
+            if (nums[i] == 1) {
+                swap(nums, i, index);
+                index++;
+            }
+        }
+    }
+
+    private void swap(int[] nums, int x, int y) {
+        int temp = nums[x];
+        nums[x] = nums[y];
+        nums[y] = temp;
+    }
+}
+
+
+/*
+双指针：
+1、p0、p2指针分别指向首尾
+2、遍历到p2指针位置时结束，防止交换完的元素2又被错误地换到前面
+3、由于可能存在2换2的情况，使用while循环将元素2交换到尾部，确保当前位置不是元素2
+4、当前位置的元素2交换完后，再判断交换元素0到头部
+ */
+class Solution {
+    public void sortColors(int[] nums) {
+        int n = nums.length;
+        int p0 = 0, p2 = n - 1;
+        for (int i = 0; i <= p2; i++) {
+            while (i <= p2 && nums[i] == 2) {
+                swap(nums, i, p2);
+                p2--;
+            }
+            if (nums[i] == 0) {
+                swap(nums, i, p0);
+                p0++;
+            }
+        }
+    }
+
+    private void swap(int[] nums, int x, int y) {
+        int temp = nums[x];
+        nums[x] = nums[y];
+        nums[y] = temp;
+    }
+}
