python有一个整数顺序表L,设计一个尽可能高效的算法将所有的负数元素移动到其它元素的前面,并给出算法的时间和空间复杂度。
时间: 2023-05-11 09:05:13 浏览: 150
数据结构中顺序表的算法
可以使用双指针法,一个指针从前往后扫描,另一个指针从后往前扫描,当发现前面的数为负数,后面的数为非负数时,交换两个数的位置。时间复杂度为O(n),空间复杂度为O(1)。
代码如下:
def move_negative(L):
left = 0
right = len(L) - 1
while left < right:
if L[left] < 0:
left += 1
elif L[right] >= 0:
right -= 1
else:
L[left], L[right] = L[right], L[left]
left += 1
right -= 1
时间复杂度:O(n),因为只需要遍历一次整个列表。
空间复杂度:O(1),因为只需要使用两个指针来交换元素,不需要额外的空间。
阅读全文