写一段c语言代码实现在整型数组r[n]中删除所有值为x的元素,要求时间复杂度为O(n),空间复杂度O(1)。
时间: 2024-09-20 11:01:58 浏览: 41
m.rar_快速排列c
为了实现在整型数组 `r[n]` 中删除所有值为 `x` 的元素,同时保持时间复杂度为 O(n) 和空间复杂度为 O(1),我们可以采用双指针法。以下是 C 语言的代码实现:
```c
#include <stdio.h>
void removeElement(int r[], int n, int x) {
// 初始化两个指针,一个指向开始,一个指向下一个待检查位置
int left = 0, right = 0;
while (right < n) {
// 如果当前元素不是我们要删除的值,则将其移到数组的左侧
if (r[right] != x) {
r[left++] = r[right]; // 移动左指针并更新元素
}
right++; // 右指针右移
}
// 将数组右侧剩余的空间置零,以隐藏已删除的元素
for (; left < n; left++) {
r[left] = 0;
}
}
int main() {
int r[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(r) / sizeof(r[0]);
int x = 5;
printf("Before removing: ");
for (int i = 0; i < n; i++) {
printf("%d ", r[i]);
}
removeElement(r, n, x);
printf("\nAfter removing: ");
for (int i = 0; i < n; i++) {
if (r[i]) {
printf("%d ", r[i]);
} else {
printf("_", i); // 显示已删除的位置
}
}
return 0;
}
```
运行这段代码后,输入数组 `r` 中所有值为 `5` 的元素会被删除,其他元素保持不变。注意,由于我们无法直接改变数组大小,所以实际上是用 `0` 来替换被删除的元素,通过查看非零元素来判断哪些元素已被删除。
阅读全文