“This is the 13th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

I didn’t fall asleep until 3:30 p.m., so IT was a bit of a fog and a bit of a fog when I woke up this morning to join Weekly Contest 277. The fourth gave up without a clue. This is the second question in the Weekly Contest 277. On Medium, it examines the flexible use of the double pointer. Again, it’s not very difficult.

describe

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, 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.Copy the code

Note:

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.
Copy the code

parsing

Given an array of integers, nums, indexed by 0, of even length, consisting of equal numbers of positive and negative integers. We are asked to rearrange the elements of numS and return them so that the modified array conforms to the given condition:

  • Each pair of consecutive integers has the opposite sign.
  • For all integers with the same sign, the order in which they appear in NUMS is preserved.
  • The rearranged array begins with a positive integer.

The most violent method is to initialize two lists, A and B. A stores the left-to-right positive integers in NUMS, and B stores the left-to-right negative integers in NUMS. Since the two lists are of equal length, we just need to take the first element from A. I take the first element from B, and then I take the second element from A, and THEN I take the second element from B, and I loop through this process and I get the result, but this method times out, so the time of this algorithm is O(N), and I didn’t know what was going on, so I had to switch to a double pointer.

To ensure that the new NUMs can have consecutive integers with opposite signs, and that their sequential positions are preserved, the simplest idea is to use two Pointers p and N, one for positive integers and one for negative integers, to traverse all elements in nums from left to right, adding positive integers to the new list first. Find the negative integer and add it to the list, then find the next positive integer, then the next negative integer, and repeat the process until all the elements are found, and the new list result is equivalent to a new arrangement of the problem. The time is order N.

In fact, the violent solution than the double pointer solution more than a traversal process, is it because this more than a traversal on the timeout? Don’t understand?

answer

class Solution(object):
    def rearrangeArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = []
        N = len(nums)
        idx_p = 0
        idx_n = 0
        while len(result)<N:
            while nums[idx_p]<0:
                idx_p += 1
            result.append(nums[idx_p])
            idx_p += 1
            while nums[idx_n]>0:
                idx_n += 1
            result.append(nums[idx_n])
            idx_n += 1
        return result
            
        	      
		
Copy the code

The results

133/133 Test cases passed. Status: Accepted Runtime: 1512 MS Memory Usage: 46.5 MBCopy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation