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

• 这就是 std::unique 的功能

class Solution {
 public:
  int removeDuplicates(vector<int>& nums) {
    return unique(begin(nums), end(nums)) - begin(nums);
  }
};

• 原理如下

[0,0,1,1,1,2,2,3,3,4]
[0,1,1,1,1,2,2,3,3,4]  // 找到 0 之后第一个不与 0 重复的元素 1，复制 0 之后
[0,1,2,1,1,2,2,3,3,4]  // 找到 1 之后第一个不与 1 重复的元素 2，复制 1 之后
[0,1,2,3,1,2,2,3,3,4]  // 找到 2 之后第一个不与 2 重复的元素 3，复制 2 之后
[0,1,2,3,4,2,2,3,3,4]  // 找到 3 之后第一个不与 3 重复的元素 4，复制 3 之后
// 返回最后一个不重复元素（即 4）的后一位置（4 之后第一个 2）的迭代器

• 不使用 STL 的解法如下

class Solution {
 public:
  int removeDuplicates(vector<int>& nums) {
    if (empty(nums)) {
      return 0;
    }
    int l = 0;
    for (int r = 1; r < size(nums); ++r) {
      if (nums[l] != nums[r]) {
        ++l;
        if (l < r) {
          nums[l] = nums[r];
        }
      }
    }
    return l + 1;
  }
};