Merge pull request chefyuan#17 from liyupi/patch-1

chefyuan · web-flow · commit e8255d73ec70 · 2021-04-26T19:37:47.000+08:00
Update 荷兰国旗.md
diff --git a/animation-simulation/数据结构和算法/荷兰国旗.md b/animation-simulation/数据结构和算法/荷兰国旗.md
@@ -72,6 +72,8 @@
 
 下面我们直接看代码吧，和三向切分基本一致。
 
+Java Code：
+
 ```java
 class Solution {
     public void sortColors(int[] nums) {
@@ -99,6 +101,37 @@ class Solution {
 }
 ```
 
+C++ Code：
+
+```c++
+class Solution {
+public:
+    void sortColors(vector<int>& nums) {
+        int len = nums.size();
+        int left = 0;
+        //这里和三向切分不完全一致
+        int i = left;
+        int right = len-1;
+        
+        while (i <= right) {
+            if (nums[i] == 2) {
+                swap(nums,i,right--);
+            } else if (nums[i] == 0) {
+                swap(nums,i++,left++);
+            } else {
+                i++;
+            }
+        }
+    }
+
+    void swap (vector<int>& nums, int i, int j) {
+        int temp = nums[i];
+        nums[i] = nums[j];
+        nums[j] = temp;
+    }
+};
+```
+
 另外我们看这段代码，有什么问题呢？那就是我们即使完全符合时，仍会交换元素，这样会大大降低我们的效率。
 
 例如：[0,0,0,1,1,1,2,2,2]
@@ -117,6 +150,8 @@ class Solution {
 
 另一种代码表示
 
+Java Code：
+
 ```java
 class Solution {
     public void sortColors(int[] nums) {
@@ -148,5 +183,38 @@ class Solution {
 }
 ```
 
+C++ Code：
+
+```c++
+class Solution {
+public:
+    void sortColors(vector<int>& nums) {
+        int left = 0;
+        int len = nums.size();
+        int right = len - 1;
+        for (int i = 0; i <= right; ++i) {
+            if (nums[i] == 0) {             
+                swap(nums,i,left);
+                left++;
+            }
+            if (nums[i] == 2) {
+                swap(nums,i,right);
+                right--;
+                //如果不等于 1 则需要继续判断，所以不移动 i 指针，i--
+                if (nums[i] != 1) {
+                    i--;
+                }
+            }
+        }
+        
+    }
+    void swap (vector<int>& nums, int i, int j) {
+        int temp = nums[i];
+        nums[i] = nums[j];
+        nums[j] = temp;
+    }
+};
+```
+
 好啦，这个问题到这就结束啦，是不是很简单啊，我们明天见！
 
