某顺序表中存放若干正整数(个数不超过1000),设计尽可能高效的算法,删除所有值为e的元素,并输出删除后的顺序表。要求删除后的元素,前后相对关系不变。
时间: 2024-05-02 13:18:41 浏览: 21
算法思路:
由于删除元素后前后相对关系不能改变,所以可以采用“覆盖”的方式进行删除。具体步骤如下:
1. 从表头开始扫描顺序表,若遇到值为e的元素,将其覆盖为下一个元素,并将扫描指针i减1,相当于将删除的元素跳过。
2. 如果当前元素不是要删除的元素,则继续扫描下一个元素。
3. 扫描完整个顺序表后,将表尾多余的元素删除。
4. 输出删除后的顺序表。
算法实现:
```python
def delete_element(seq_list, e):
n = len(seq_list)
i = 0 # 扫描指针
while i < n:
if seq_list[i] == e:
# 覆盖删除,相当于将删除的元素跳过
for j in range(i, n-1):
seq_list[j] = seq_list[j+1]
n -= 1 # 表长减1
i -= 1 # 扫描指针减1,继续扫描当前位置
i += 1 # 扫描下一个位置
seq_list = seq_list[:n] # 删除表尾多余的元素
return seq_list
```
算法分析:
由于每个元素最多只遍历一遍,时间复杂度为O(n)。由于只使用常数个辅助变量,空间复杂度为O(1)。因此,该算法是高效的。
相关问题
一个整数顺序表L,设计一个尽可能高效的算法删除其中所有值为负数的元素:python算法实现
可以使用双指针法,将非负数元素移到前面,然后修改列表长度即可。具体实现如下:
```python
def remove_negative(L):
i, j = 0, 0
while j < len(L):
if L[j] >= 0:
L[i] = L[j]
i += 1
j += 1
del L[i:]
```
一个整数顺序表L,设计一个尽可能高效的算法将其中所有值为负数移到其他元素前面
可以使用双指针法,一个指针从前往后扫描,一个指针从后往前扫描,当两个指针都扫描到负数和正数时,交换它们的位置,直到两个指针相遇为止。时间复杂度为O(n)。
代码示例:
```
void moveNegative(int L[], int n) {
int i = 0, j = n - 1;
while (i < j) {
while (i < j && L[i] < 0) i++;
while (i < j && L[j] >= 0) j--;
if (i < j) {
int temp = L[i];
L[i] = L[j];
L[j] = temp;
}
}
}
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)