去除有序数组中重复的元素
题目描述:给定一个长度为len的数组arr,去除其中重复的元素,并返回剩余元素的个数。要求时间复杂度为O(n),空间复杂度为O(1)。
分析:已知数组arr是有序的,最简单的思路是对数组进行遍历,遇到重复的元素删除掉,然后将剩余元素前移。这样做不满足时间复杂度为O(n),所以我们还得另想其他方法。
在遍历数组的时候对问题进行拆分,即:
- 当前元素和下一个元素相等
- 当前元素和下一个元素不相等
我们可以从数组的第2个元素开始遍历,并用index记录数组中不相等元素的下标
- 如果当前元素和前一个元素相等,什么都不做。
- 如果不相等,将当前元素替换掉index所指的元素,然后index + 1
最后index即为剩余元素的个数
代码实现:
拓展:一个有序数组中,允许某个数最多重复2次,计算去重后的数组。
代码实现: