编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1)。 非递减顺序表举例:{2 2 2 3 4 4 5 5 6 6} 用c语言写
时间: 2023-05-29 15:07:33 浏览: 131
void removeDuplicates(int* L, int len) {
int i, j;
for (i = 0, j = 1; j < len; j++) {
if (L[i] != L[j]) {
L[++i] = L[j];
}
}
// 将末尾多余的元素删除
len = i + 1;
}
// 示例
int main() {
int L[] = {2, 2, 2, 3, 4, 4, 5, 5, 6, 6};
int len = sizeof(L) / sizeof(int);
removeDuplicates(L, len);
for (int i = 0; i < len; i++) {
printf("%d ", L[i]);
}
return 0;
}
// 输出:2 3 4 5 6
相关问题
编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1)。、
1. 初始化两个指针i和j,初始值为0。
2. 从第二个元素开始遍历顺序表L,如果当前元素与前一个元素相等,则j指针向后移动。
3. 如果当前元素与前一个元素不相等,则将当前元素复制到i+1位置,i指针向后移动一位,j指针向后移动一位。
4. 重复步骤2和3,直到遍历完整个顺序表L。
5. 将i指针后面的元素全部删除,即将顺序表L的长度修改为i+1。
算法实现:
```
void removeDuplicates(List& L) {
int i = 0, j = 0;
int n = L.length();
while (j < n) {
if (L[j] == L[i]) {
j++;
} else {
i++;
L[i] = L[j];
j++;
}
}
L.resize(i + 1);
}
```
时间复杂度为O(n),空间复杂度为O(1)。
编写算法,在一非递减的顺序表中,删除所有值相等的多余元素。要求时间复杂度为o(n),空间复杂度为o(1)。
算法步骤如下:
1. 定义两个指针i和j,初始值均为1。
2. 从第二个元素开始,依次遍历整个顺序表。
3. 如果当前元素与前一个元素相等,则将j指针后移一位。
4. 如果当前元素与前一个元素不相等,则将i指针后移一位,并将i指向的元素替换为j指向的元素。
5. 重复步骤3和4,直到遍历完整个顺序表。
6. 最后,将顺序表的长度更新为i的值。
这个算法的时间复杂度为O(n),空间复杂度为O(1)。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)