用c语言编写,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1);
时间: 2023-05-19 10:06:23 浏览: 96
编写算法清除顺序表L中所有重复的数据元素
5星 · 资源好评率100%
可以使用双指针法来实现这个算法。定义两个指针i和j,初始时i=0,j=1。从第二个元素开始,如果L[j]与L[i]相等,则j++;否则,将L[j]赋值给L[i+1],i++,j++。最后,将L的长度设置为i+1即可。这个算法的时间复杂度为O(n),空间复杂度为O(1)。
以下是代码实现:
void removeDuplicates(int *L, int n) {
int i = 0, j = 1;
while (j < n) {
if (L[j] == L[i]) {
j++;
} else {
L[++i] = L[j++];
}
}
n = i + 1;
}
阅读全文