编写一个函数,从一给定的顺序表A中删除值在x~y(x≤y)之间的所有元素,要求以较高的效率来实现。
时间: 2024-05-06 14:20:01 浏览: 10
算法思路:
这里提供两种算法思路:
1.双指针法
定义两个指针i和j,初始时i指向0,j指向表尾。从头到尾扫描表A,当A[i]的值在x~y之间时,i指针向后移动一位,将A[j]的值赋给A[i],j指针向前移动一位;否则i指针向后移动一位。当i>=j时扫描结束。
2.快慢指针法
定义两个指针i和j,初始时i和j都指向0,从头到尾扫描表A。当A[j]的值不在x~y之间时,j指针向后移动一位;否则i指针向后移动一位,将A[j]的值赋给A[i],j指针向后移动一位。当j扫描结束时,i即为新表的长度。
Python代码实现:
双指针法:
```python
def delete_elements(A, x, y):
i, j = 0, len(A)-1
while i <= j:
if x <= A[i] <= y:
A[i] = A[j]
j -= 1
else:
i += 1
return A[:i]
```
快慢指针法:
```python
def delete_elements(A, x, y):
i, j = 0, 0
while j < len(A):
if x <= A[j] <= y:
A[i] = A[j]
i += 1
j += 1
return A[:i]
```
注意:以上代码实现都是删除x~y之间的元素,如果要删除x~y之外的元素,只需要将if条件取反即可。