假设我们有一个感测器，会不停地向 HQ 传输已经归类好数据，数据的格式全部是数字（种类编号），且已经按照从小到大的顺序排列，大概是 [1,1,4,5,7,9] 这样的，但是我们的需求在于，希望知道有多少个种类，那么该如何解决呢？

如果这样一个问题放在关系型资料库中操作的话就非常方便了，学过 SQL 语言的同学很快就会想到 DISTINCT 关键字，剩下的就是拼接一下 SELECT 语句出来就好了，但是如果我们的问题不是 SQL 相关的呢？

力扣（LeetCode） 中 "26.删除排序数组中的重复项" 正是一个类似要求的题目。

Loading...?

leetcode-cn.com图标

注意在题目当中要求的是：不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成，意味著不能通过新建数组存放的方式解决，那么对于这样一个问题我们该如何解决呢？

可以考虑增加一个游标的方式（命名为：index），遍历整个数组，当遇到前一个和后一个不相等的时候就给游标自增，这样的话对于相同的元素可以直接跳过不统计，最后返回」游标的大小+1「（也即不重复的元素的个数），代码实现如下：

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty())
return 0;

int index = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[index] != nums[i])
nums[++index] = nums[i];
}
return index + 1;
}

这样的话就符合了题目所要求的各个复杂度以及就地统计的原则，当然，如果你对 STL 比较熟悉的话这道题其实可以偷懒一下：

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

比较容易是不是？我们对题目做一点改变，由于感测器有一个误差的区间，对于所有可能的种类我们允许它最多出现两次，认为是不同的两个种类，这样的话问题该如何解决呢？

由于要求是两次，所以我们可以考虑通过增加一个变数的方式来记录种类编号出现的次数就可以了嘛，代码实现如下：

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() <= 2)
return nums.size();

int index = 2;
for (int i = 2; i < nums.size(); i++){
if (nums[i] != nums[index - 2])
nums[index++] = nums[i];
}
return index;
}
};

这样的话我们又可以正确地统计到种类个数了。

以上是 力扣（LeetCode）中两道题目 "26.删除排序数组中的重复项" 和 "80.删除排序数组中的重复项 II"的拓展，由于这两道题是从简单到复杂的的一个过程，从对于题目的解答中我们可以慢慢培养接近一个问题的解决方案的思路，掌握了解决特定情况问题的方法之后，就可以慢慢得到一个通用问题的解决方案，一次次迭代下去，想到新的思路就比较容易了。

本文作者：Nova

声明：本文归 「力扣」 版权所有，如需转载请联系。

推荐阅读：

相关文章