一个未排序整数数组,有正负数,重新排列使负数排在正数前面。并且要求不改变原来的正负数之间相对顺序。比如输入1、7、-5、9、-12、15,输出-5、-12、1、7、9、15。
时间: 2023-03-22 19:04:14 浏览: 78
可以使用双指针法,一个指针从数组头开始,一个指针从数组尾开始,分别向中间移动,直到两个指针相遇。在移动指针的过程中,如果左指针指向的数是正数,右指针指向的数是负数,就交换这两个数的位置。如果左指针指向的数是负数,就继续向右移动;如果右指针指向的数是正数,就继续向左移动。这样可以保证负数排在正数前面,并且不改变原来的正负数之间相对顺序。
相关问题
js中数组排列数组里的正数和负数排序
可以使用JavaScript的sort()方法来对数组进行排序,可以按照以下步骤来排列数组里的正数和负数:
1. 使用sort()方法对数组进行排序,可以使用一个比较函数作为参数来告诉sort()方法如何排序。
2. 比较函数应该返回一个负数、零或正数,表示两个元素之间的相对顺序。如果返回负数,则第一个元素应该排在第二个元素之前;如果返回正数,则第一个元素应该排在第二个元素之后;如果返回零,则两个元素的相对顺序不变。
3. 在比较函数中,可以根据元素的正负性来判断它们的顺序。如果两个元素都是正数或都是负数,则按照它们的大小来排序;如果一个元素是正数,另一个是负数,则将负数放在正数前面。
例如,下面的代码可以将数组里的正数和负数分别排列,并且正数按照从小到大的顺序排序,负数按照从大到小的顺序排序:
```
let arr = [3, -2, 5, -1, 4, -6];
arr.sort((a, b) => {
if (a >= 0 && b >= 0) {
return a - b;
} else if (a < 0 && b < 0) {
return b - a;
} else if (a >= 0 && b < 0) {
return -1;
} else {
return 1;
}
});
console.log(arr); // [-1, 3, 4, 5, -2, -6]
```
在上面的代码中,如果a和b都是正数,则返回它们的差;如果a和b都是负数,则返回b和a的差;如果a是正数,b是负数,则将负数放在正数前面,返回-1;如果a是负数,b是正数,则将负数放在正数前面,返回1。这样就可以将数组里的正数和负数分别排列,并且正数按照从小到大的顺序排序,负数按照从大到小的顺序排序。
缺失的第一个正数 给定一个未排序的整数数组 nums ,找出其中没有出现过的最小的正整数 要求:时间复杂度为O(n)
可以使用桶排序的思想来解决这个问题。
首先,我们可以遍历一遍数组,把所有正整数放入一个桶中,桶的下标为该正整数减一(因为数组下标从0开始,而正整数从1开始)。比如,如果数组中有3这个正整数,我们就将桶中的第2个元素(下标为2)标记为已经存在。这样,桶中第一个没有被标记的元素就是最小的未出现过的正整数。
接下来,再遍历一遍桶,找出第一个没有被标记的元素的下标,并返回该下标加一即可。如果所有桶都被标记了,说明数组中的所有正整数都出现过,此时最小的未出现过的正整数为数组长度加一。
以下是代码实现:
```python
def firstMissingPositive(nums):
n = len(nums)
# 将所有负数和0都视为不存在的数,因为我们要找的是最小的正整数
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
# 将所有存在的正整数对应的桶标记为已经存在
for i in range(n):
num = abs(nums[i])
if num <= n:
nums[num - 1] = -abs(nums[num - 1])
# 找到第一个没有被标记的桶的下标,即为最小的未出现过的正整数
for i in range(n):
if nums[i] > 0:
return i + 1
# 如果所有桶都被标记了,说明数组中的所有正整数都出现过,此时最小的未出现过的正整数为数组长度加一
return n + 1
```
时间复杂度为O(n),空间复杂度为O(1)。