2149-按符号重排数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。

你需要 重排 nums 中的元素，使修改后的数组满足下述条件：

  1. 任意 连续 的两个整数 符号相反
  2. 对于符号相同的所有整数， 保留 它们在 nums 中的 顺序 。
  3. 重排后数组以正整数开头。

重排元素满足上述条件后，返回修改后的数组。

示例 1：

**输入：** nums = [3,1,-2,-5,2,-4]
**输出：** [3,-2,1,-5,2,-4]
**解释：**
nums 中的正整数是 [3,1,2] ，负整数是 [-2,-5,-4] 。
重排的唯一可行方案是 [3,-2,1,-5,2,-4]，能满足所有条件。
像 [1,-2,2,-5,3,-4]、[3,1,2,-2,-5,-4]、[-2,3,-5,1,-4,2] 这样的其他方案是不正确的，因为不满足一个或者多个条件。

示例 2：

**输入：** nums = [-1,1]
**输出：** [1,-1]
**解释：**
1 是 nums 中唯一一个正整数，-1 是 nums 中唯一一个负整数。
所以 nums 重排为 [1,-1] 。

提示：

  • 2 <= nums.length <= 2 * 105
  • nums.length 是 偶数
  • 1 <= |nums[i]| <= 105
  • nums 由 相等 数量的正整数和负整数组成

方法一：双指针

思路与算法

我们可以使用两个指针对数组 left 进行遍历，其中指针 pos 负责遍历所有的正数，指针 neg 负责遍历所有的负数。

记数组 nums 的长度为 n，那么其中分别包含 n/2 个正数和负数。因此我们只需要重复如下操作 n/2 次：

  • 指针 pos 不断向后移动，直到遇到一个正数为止，并将该正数放入答案数组；

  • 指针 neg 不断向后移动，直到遇到一个负数为止，并将该负数放入答案数组。

pos 和 neg 初识时均指向 nums 的首个元素。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int n = nums.size();
        int pos = 0, neg = 0;
        vector<int> ans;
        for (int i = 0; i + i < n; ++i) {
            while (nums[pos] < 0) {
                ++pos;
            }
            ans.push_back(nums[pos]);
            ++pos;
            while (nums[neg] > 0) {
                ++neg;
            }
            ans.push_back(nums[neg]);
            ++neg;
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pos = neg = 0
        ans = list()

        for i in range(n // 2):
            while nums[pos] < 0:
                pos += 1
            ans.append(nums[pos])
            pos += 1
            while nums[neg] > 0:
                neg += 1
            ans.append(nums[neg])
            neg += 1
        
        return ans
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func rearrangeArray(nums []int) []int {
	n := len(nums)
	pos, neg, ans := 0, 0, []int{}

	for i := 0; i+i < n; i++ {
		for ; nums[pos] < 0; pos++ {
		}
		ans = append(ans, nums[pos])
		pos++
		for ; nums[neg] > 0; neg++ {
		}
		ans = append(ans, nums[neg])
		neg++
	}

	return ans
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(1)。这里不计入返回值需要使用的空间。

 Comments
On this page
2149-按符号重排数组