2026/05/14

[LeetCode] 75 Sort Colors

這演算法也太可愛

居然還有名字Dutch National Flag Algorithm!!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
  void sortColors(vector<int> &nums) {
    int low = 0;
    int mid = 0;
    int high = nums.size() - 1;
    while (mid <= high) {
      if (nums[mid] == 0) {
        std::swap(nums[low], nums[mid]);
        low++;
        mid++;
      } else if (nums[mid] == 1)
        mid++;
      else {
        std::swap(nums[mid], nums[high]);
        high--;
      }
    }
  }
};
Labels: