某顺序表中存放若干正整数(个数不超过1000),设计尽可能高效的算法,删除所有值为e的元素,并输出删除后的顺序表。要求删除后的元素,前后相对关系不变。
时间: 2024-05-02 17:18:41 浏览: 101
算法思路:
由于删除元素后前后相对关系不能改变,所以可以采用“覆盖”的方式进行删除。具体步骤如下:
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)。因此,该算法是高效的。
阅读全文