feat: azl397985856#75 A better solution with O(n) (azl397985856#280)

jojoxiaojing · azl397985856 · azl397985856 · commit 81f4b13a369c · 2020-01-17T18:15:45.000+08:00
* Update 75: A better solution with O(n)

* Update 75.sort-colors.md

* Update 75.sort-colors.md

Co-authored-by: lucifer &lt;azl397985856@gmail.com&gt;
diff --git a/problems/75.sort-colors.md b/problems/75.sort-colors.md
@@ -19,77 +19,55 @@ First, iterate the array counting number of 0's, 1's, and 2's, then overwrite ar
 Could you come up with a one-pass algorithm using only constant space?
 
 ## 思路
+这个问题是典型的荷兰国旗问题 （https://en.wikipedia.org/wiki/Dutch_national_flag_problem）。 因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。
 
-其实就是排序，而且没有要求稳定性，就是用啥排序算法都行。
-题目并没有给出数据规模，因此我默认数据量不大，直接选择了冒泡排序
-
-## 关键点解析
-
-冒泡排序的时间复杂度是N平方，无法优化，但是可以进一步优化常数项，
-比如循环的起止条件。 由于每一次遍历都会将最后一位“就位”，因此内层循环的截止条件就可以是
- `nums.length - i`， 而不是 `nums.length`, 可以省一半的时间。
-
-
-## 代码
-
-```js
-/*
- * @lc app=leetcode id=75 lang=javascript
- *
- * [75] Sort Colors
- *
- * https://leetcode.com/problems/sort-colors/description/
- *
- * algorithms
- * Medium (41.41%)
- * Total Accepted:    297K
- * Total Submissions: 716.1K
- * Testcase Example:  '[2,0,2,1,1,0]'
- *
- * Given an array with n objects colored red, white or blue, sort them in-place
- * so that objects of the same color are adjacent, with the colors in the order
- * red, white and blue.
- * 
- * Here, we will use the integers 0, 1, and 2 to represent the color red,
- * white, and blue respectively.
- * 
- * Note: You are not suppose to use the library's sort function for this
- * problem.
- * 
- * Example:
- * 
- * 
- * Input: [2,0,2,1,1,0]
- * Output: [0,0,1,1,2,2]
- * 
- * Follow up:
- * 
- * 
- * A rather straight forward solution is a two-pass algorithm using counting
- * sort.
- * First, iterate the array counting number of 0's, 1's, and 2's, then
- * overwrite array with total number of 0's, then 1's and followed by 2's.
- * Could you come up with a one-pass algorithm using only constant space?
- * 
- * 
- */
-/**
- * @param {number[]} nums
- * @return {void} Do not return anything, modify nums in-place instead.
- */
-var sortColors = function(nums) {
-    function swap(nums, i, j) {
-       const temp = nums[i];
-       nums[i] = nums[j];
-       nums[j] = temp; 
-    }
-    for (let i = 0; i < nums.length - 1; i++) {
-        for (let j = 0; j < nums.length - i; j++) {
-            if (nums[j] < nums[j -1]) {
-                swap(nums, j - 1 , j)
-            }
-            
-        }      
-    }
-};
+有两种解决思路。
+
+## 解法一
+- 遍历数组，统计红白蓝三色球（0，1，2）的个数
+- 根据红白蓝三色球（0，1，2）的个数重排数组
+
+这种思路的时间复杂度：$O(n)$，需要遍历数组两次。
+
+## 解法二
+
+我们可以把数组分成三部分，前部（全部是0），中部（全部是1）和后部（全部是2）三个部分。每一个元素（红白蓝分别对应0、1、2）必属于其中之一。将前部和后部各排在数组的前边和后边，中部自然就排好了。
+
+我们用三个指针，设置两个指针begin指向前部的末尾的下一个元素（刚开始默认前部无0，所以指向第一个位置），end指向后部开头的前一个位置（刚开始默认后部无2，所以指向最后一个位置），然后设置一个遍历指针current，从头开始进行遍历。
+
+这种思路的时间复杂度也是$O(n)$, 只需要遍历数组一次。
+
+### 关键点解析
+
+
+- 荷兰国旗问题
+- counting sort
+
+### 代码
+
+代码支持： Python3
+
+Python3 Code:
+
+``` python
+class Solution:
+    def sortColors(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        p0 = cur = 0
+        p2 = len(nums) - 1
+        
+        while cur <= p2:
+            if nums[cur] == 0:
+                nums[cur], nums[p0] = nums[p0], nums[cur]
+                p0 += 1
+                cur += 1
+            elif nums[cur] == 2:
+                nums[cur], nums[p2] = nums[p2], nums[cur]
+                p2 -= 1
+            else:
+                cur += 1
 ```
+
+
