有一个整数顺序表L,用python设计一个尽可能高效的算法将所有的负数元素移动到其它元素的前面,并给出算法的时间和空间复杂度。
时间: 2023-05-11 12:04:40 浏览: 134
已知线性表按顺序存于内存,每个元素都是整数,试设计把所有值为负数的元素移到全部正数值元素前边的算法 .cpp
可以使用双指针的方法,一个指针从前往后扫描,另一个指针从后往前扫描,当前面的指针指向的元素为负数,后面的指针指向的元素为非负数时,交换两个元素的位置,直到两个指针相遇为止。这样就可以将所有负数移动到前面了。
时间复杂度为O(n),空间复杂度为O(1)。
以下是Python代码实现:
def move_negative(L):
left = 0
right = len(L) - 1
while left < right:
while left < right and L[left] < 0:
left += 1
while left < right and L[right] >= 0:
right -= 1
if left < right:
L[left], L[right] = L[right], L[left]
return L
阅读全文