leetcode - 2149. Rearrange Array Elements by Sign

这篇具有很好参考价值的文章主要介绍了leetcode - 2149. Rearrange Array Elements by Sign。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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:

  1. Every consecutive pair of integers have opposite signs.
  2. For all integers with the same sign, the order in which they were present in nums is preserved.
  3. 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.

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode //189. Rotate Array

    Given an integer array nums , rotate the array to the right by k steps, where k is non-negative.   Example 1: Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Example 2: Input: nums = [-1,-100,3,99],

    2024年02月13日
    浏览(40)
  • LeetCode //88. Merge Sorted Array

    You are given two integer arrays nums1 and nums2 , sorted in non-decreasing order, and two integers m and n , representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1

    2024年02月12日
    浏览(45)
  • LeetCode --- 1929. Concatenation of Array 解题报告

    Given an integer array  nums  of length  n , you want to create an array  ans  of length  2n  where  ans[i] == nums[i]  and  ans[i + n] == nums[i]  for  0 = i n  ( 0-indexed ). Specifically,  ans  is the  concatenation  of two  nums  arrays. Return  the array  ans . Example 1: Example 2:

    2024年02月09日
    浏览(54)
  • Leetcode array 704 27 189 121 380 238 134 13

    二分搜索: 判断条件是left 和 right 这里就要注意区间开闭的问题 因为需要运行时间时O(1),所以要加上map 删除的时候要把需要删除的变到最后,再直接pop掉 rand用法: 1.rand() 2. nums[rand() % nums.size()]; 3. left+rand() % (right-left)

    2024年02月09日
    浏览(35)
  • 【递增栈】个人练习-Leetcode-845. Longest Mountain in Array

    题目链接:https://leetcode.cn/problems/longest-mountain-in-array/ 题目大意:给出一个数组 arr[] ,定义【山数组】为【长度大于等于3】【前面部分递增,后面部分递减,存在一个山峰元素】的数组。求 arr[] 中的最长的是【山数组】的子列。 思路:递增栈当然可以,不过刚好想到另一个

    2024年02月06日
    浏览(53)
  • LeetCode //80. Remove Duplicates from Sorted Array II

    Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums

    2024年02月13日
    浏览(50)
  • leetcode - 852. Peak Index in a Mountain Array

    An array arr a mountain if the following properties hold: You must solve it in O(log(arr.length)) time complexity. Example 1: Example 2: Example 3: Constraints: Use binary search to solve this problem. For any middle index, it either locates at the left of the peak, or the right of the peak. If at the left, then discard the left half, otherwise discard the r

    2024年02月15日
    浏览(36)
  • LeetCode //167. Two Sum II - Input Array Is Sorted

    Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 = index1 index2 numbers.length. Return the indices of the two numbers, index1 and index2 , added by one as an integer array [index1

    2024年02月15日
    浏览(55)
  • LeetCode //C - 153. Find Minimum in Rotated Sorted Array

    Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n

    2024年02月06日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包