Li Kou today's question -324 Swing sort II

324. Swing sort II

Sort + Double pointer

Ideas ：

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        // take nums Clone to new array newArry
        int[] newArry = nums.clone();
        // take newArray Sort 
        Arrays.sort(newArry);
        // Define the position of the two pointers 
        int left = (newArry.length-1)/2,right = newArry.length-1;
        // Start inserting data , First insert left The element of the pointer （ Small ）, In the insert right The element that the pointer points to （ Big ）
        for(int i = 0; i<nums.length;i++){
    
            if(i%2 == 0){
    
                nums[i] = newArry[left];
                left--;
            }else{
    
                nums[i] = newArry[right];
                right--;
            }
        }
    }
}

One dimensional array copy mode clone

Bucket sort

We can divide all the elements into buckets and take them out one by one . Because the maximum data size is 5000, We can drive 5001 A bucket to hold elements . Then put back the original array from large to small .

Tips

Use another array as a bucket , Subscripts are used to record value , Value is used to record Number of this value .

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        // Bucket sort 
        //1. First define a bucket , Capacity depends on the problem , The biggest is 5000
        int[] bucket = new int[5001] ;
        //2. Sort the data in buckets 
        for(int num : nums){
    
            //num  Get is nums  In the value of the ,bucket[nums] Is to take the data as a subscript , The number of occurrences of values as data 
            bucket[num]++;
        }
        // Define a variable , It will be used to get the value in the bucket later . 
        int j = 5000;
        //3.  Start to set the value , discharge 1,3,5,7..... These are all places of great value 
        for(int i = 1; i < nums.length ; i +=2 ){
    
            // First find the meaningful data in the bucket 
            while(bucket[j] == 0){
    
                // These are meaningless data , Quick skip , The subscript goes back 
                j--;
            }
            // Encountered data , Start assignment 
            nums[i] = j;
            bucket[j]--;
        }
        //4.  Reduce data ,0,2,4,6,.....
        for(int i = 0 ; i < nums.length; i += 2){
    
            while(bucket[j] == 0){
    
                j--;
            }
            nums[i] = j;
            bucket[j]--;
        }


    }
}

Suggest

Let's do it , Although it is of medium difficulty , But using the right method is not difficult .