yulu

算法-去除有序数组中重复的元素

发表于
去除有序数组中重复的元素

题目描述：给定一个长度为len的数组arr，去除其中重复的元素，并返回剩余元素的个数。要求时间复杂度为O(n)，空间复杂度为O(1)。

分析：已知数组arr是有序的，最简单的思路是对数组进行遍历，遇到重复的元素删除掉，然后将剩余元素前移。这样做不满足时间复杂度为O(n),所以我们还得另想其他方法。
在遍历数组的时候对问题进行拆分，即：

  1. 当前元素和下一个元素相等
  2. 当前元素和下一个元素不相等

我们可以从数组的第2个元素开始遍历,并用index记录数组中不相等元素的下标

  • 如果当前元素和前一个元素相等，什么都不做。
  • 如果不相等，将当前元素替换掉index所指的元素，然后index + 1

最后index即为剩余元素的个数

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main()
{
	int arr[] = {2,2,3,5,5,5,7,9,9};
	int index = 1;
	for (int i = 1; i < sizeof(arr) / sizeof(arr[0]); i++){
		if(arr[i] != arr[index - 1]){
			arr[index] = arr[i];
			index ++;
		}	
	}
	printf("%d",index);
	return 0;
}

拓展：一个有序数组中，允许某个数最多重复2次，计算去重后的数组。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main()
{
	int arr[] = {2,2,3,5,5,5,7,9,9};
	int index = 2; //允许重复n次，index = n
	for (int i = 2; i < sizeof(arr) / sizeof(arr[0]); i++){
		if(arr[i] != arr[index - 2]){
			arr[index] = arr[i];
			index ++;
		}	
	}
	printf("%d",index);
	return 0;
}