删除顺序表中所有重复的元素,使表中所有元素的值均不同。要求算法复杂度为O(n)
时间: 2024-03-25 15:36:34 浏览: 18
可以使用双指针法,遍历顺序表并判断当前元素是否重复,如果重复则将后面的元素向前移动,直到不重复为止。具体步骤如下:
1. 定义两个指针i和j,初始值都为1。
2. 遍历顺序表,如果当前元素与前一个元素不相等,则将当前元素赋值给j所指向的位置,并将j指针后移一位。
3. 如果当前元素与前一个元素相等,则将i指针后移一位,直到找到下一个不相等的元素,并将其赋值给j所指向的位置,并将j指针后移一位。
4. 最终j指针所指向的位置即为不重复元素的个数。
时间复杂度为O(n),空间复杂度为O(1)。以下是示例代码:
```c
void deleteDuplicate(int a[], int n) {
int i, j;
j = 1;
for (i = 1; i < n; i++) {
if (a[i] != a[i-1]) {
a[j] = a[i];
j++;
}
}
}
```
相关问题
编写算法,实现从顺序表L中删除所有值介于x和y之间的元素,要求空 间复杂度为O(1)
算法思路:
1. 用两个指针i和j分别指向第一个元素
2. 当L[i]>=x且L[i]<=y时,i指针不动,j指针向后移动一位
3. 当L[i]<x或L[i]>y时,将L[j]复制到L[i]上,i和j指针同时向后移动一位
4. 重复执行2-3步骤,直到j指针超出顺序表L的范围
5. 返回新的顺序表L,其中所有值介于x和y之间的元素已被删除
代码实现:
```python
def del_between_x_and_y(L, x, y):
i = 0
j = 0
while j < len(L):
if L[j] >= x and L[j] <= y:
j += 1
else:
L[i] = L[j]
i += 1
j += 1
return L[:i]
```
时间复杂度为O(n),空间复杂度为O(1)。
顺序表 删除重复 编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1)。、
算法思路:
由于顺序表是非递减的,因此相同的元素一定是相邻的,可以使用双指针法来进行删除操作。定义两个指针i和j,初始时i=0,j=1,表示当前要比较的两个元素。如果L[i]和L[j]不相等,则将L[j]赋值给L[i+1],i和j都加1;如果L[i]和L[j]相等,则j加1,继续比较下一个元素。重复上述操作,直到j大于等于表长n。
算法实现:
```
void delDuplicate(SqList &L) {
int i = 0, j = 1;
while (j < L.length) {
if (L[i] != L[j]) {
L[++i] = L[j];
}
j++;
}
L.length = i + 1;
}
```
算法分析:
由于每个元素最多被访问两次,因此时间复杂度为O(n),由于只使用了常数个辅助变量,因此空间复杂度为O(1)。