Leetcode daily question - 324 Swing sort II

1. Title Description

324. Swing sort II

Give you an array of integers nums, Rearrange it into nums[0] < nums[1] > nums[2] < nums[3]… The order of .

You can assume that all input arrays can get results that meet the requirements of the topic .

Example 1：

 Input ：nums = [1,5,1,1,6,4]
 Output ：[1,6,1,5,1,4]
 explain ：[1,4,1,5,1,6]  It is also the result that meets the requirements of the topic , It can be accepted by the problem determination program .

Example 2：

 Input ：nums = [1,3,2,2,3,1]
 Output ：[2,3,1,3,1,2]

2. Problem solving ideas and codes

2.1 Their thinking

This problem needs to arrange the original array into nums[0] < nums[1] > nums[2] < nums[3] Such a large and small structure , Then we can sort the array from small to large , And cut it in the middle , The left part is smaller , The right part is larger , Then put back the array in the order of small and large , Then we can get the result . In array nums = [1,5,1,1,6,4] For example
Use left Point to the far right of the smaller part ,right Point to most of the left and right sides , use getSmaller To decide whether to choose a smaller number or a larger number

2.2 Code

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        //  Use a temporary array to hold 
        int[] tmp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
    
            tmp[i] = nums[i];
        }
        //  Sort the array 
        Arrays.sort(tmp);
        // left  Start at the far right of the smaller area 
        int left = (nums.length - 1) >> 1;
        // right  Start at the far right of the larger area  
        int right = nums.length - 1;
        //  Whether to select a smaller area 
        boolean getSmaller = true;
        for (int i = 0; i < nums.length; i++) {
    
            if (getSmaller) {
    
                //  Select smaller area ,left  The left one , and  getSmaller  Turn into false  Take a larger area next time 
                nums[i] = tmp[left--];
                getSmaller = false;
            } else {
    
                //  Select a larger area ,right  The left one , and  getSmaller  Turn into true  Take a smaller area next time 
                nums[i] = tmp[right--];
                getSmaller = true;
            }
        }
    }
}

2.3 test result

Pass the test

3. summary

• First, sort the array , And then it is divided into a smaller number area and a larger number area
• Use double pointers to select smaller and larger areas and place them in the array