将所有负数移到整数之前的算法。
时间: 2024-02-29 20:52:07 浏览: 53
所有负数置于正数前
一个简单的算法是使用双指针,一个指针从数组的开头向右移动,另一个指针从数组的末尾向左移动。当左指针指向一个正数,右指针指向一个负数时,交换两个数的位置。重复这个过程直到左指针大于等于右指针。
具体实现过程如下:
1. 初始化左指针left = 0和右指针right = 数组长度 - 1;
2. 循环直到left >= right:
- 如果nums[left]为负数,left指针右移;
- 如果nums[right]为正数,right指针左移;
- 如果nums[left]为正数,nums[right]为负数,交换nums[left]和nums[right]的值,left指针右移,right指针左移;
3. 返回排序后的数组。
代码示例:
```
def move_negatives(nums):
left, right = 0, len(nums) - 1
while left < right:
if nums[left] < 0:
left += 1
elif nums[right] >= 0:
right -= 1
else:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
```
注意:这个算法只能移动负数到整数之前,不能保证负数和正数的相对顺序不变。如果需要保持相对顺序,可以使用类似快排的分治算法,将负数和正数分别放在数组的左右两侧。
阅读全文