LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 设置左右边界，从左向右遍历，遇到 0 放到左边界并将左边界右移，遇到 2 放到右边界并将右边界左移，遇到 1 不用操作，继续访问下一个数。遍历完成后 0 全在左侧，2 全在右侧，中间就是 1

class Solution {
 public:
  void sortColors(vector<int>& nums) {
    int cur = 0;
    int l = 0;
    int r = size(nums);
    while (cur < r) {
      if (nums[cur] == 0 && nums[l] == 0) {
        ++cur;
        ++l;
      } else if (nums[cur] == 0) {
        swap(nums[cur], nums[l++]);
      } else if (nums[cur] == 2) {
        swap(nums[cur], nums[--r]);
      } else {
        ++cur;
      }
    }
  }
};

• 上述逻辑可合并如下

class Solution {
 public:
  void sortColors(vector<int>& nums) {
    int cur = 0;
    int l = 0;
    int r = size(nums);
    while (cur < r) {
      if (nums[cur] == 0) {
        swap(nums[cur++], nums[l++]);
      } else if (nums[cur] == 2) {
        swap(nums[cur], nums[--r]);
      } else {
        ++cur;
      }
    }
  }
};