Description
You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.
You should rearrange the elements of nums such that the modified array follows the given conditions:
- Every consecutive pair of integers have opposite signs.
- For all integers with the same sign, the order in which they were present in nums is preserved.
- The rearranged array begins with a positive integer.
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.
Example 1:
Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.
Example 2:
Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].
Constraints:
2 <= nums.length <= 2 * 10^5
nums.length is even
1 <= |nums[i]| <= 10^5
nums consists of equal number of positive and negative integers.
Solution
A brute force way would be: store all the positive and negative numbers separately, and fill one by one to the result.
The space complexity could be reduced by creating the return list first, then when the current number is positive, insert it to even indexes, otherwise insert it to odd indexes.文章来源:https://www.toymoban.com/news/detail-830898.html
Time complexity:
o
(
n
)
o(n)
o(n)
Space complexity:
o
(
n
)
o(n)
o(n)文章来源地址https://www.toymoban.com/news/detail-830898.html
Code
class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
pos_i, neg_i = 0, 1
res = [0] * len(nums)
for i in range(len(nums)):
if nums[i] > 0:
res[pos_i] = nums[i]
pos_i += 2
elif nums[i] < 0:
res[neg_i] = nums[i]
neg_i += 2
return res
到了这里,关于leetcode - 2149. Rearrange Array Elements by Sign的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!