力扣今日题-324. 摆动排序 II

324. 摆动排序 II

排序+双指针

思路：

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        //将nums克隆给新数组newArry
        int[] newArry = nums.clone();
        //将newArray进行排序
        Arrays.sort(newArry);
        //定义两个指针的位置
        int left = (newArry.length-1)/2,right = newArry.length-1;
        //开始插入数据，先插入left指针的元素（小），在插入right指针指向的元素（大）
        for(int i = 0; i<nums.length;i++){
    
            if(i%2 == 0){
    
                nums[i] = newArry[left];
                left--;
            }else{
    
                nums[i] = newArry[right];
                right--;
            }
        }
    }
}

一维数组的拷贝方式clone

桶排序

我们可以把所有的元素分桶然后逐个取出。由于数据大小最大是5000，我们可以开5001个桶来存放元素。然后从大到小依次放回原数组。

提示

用另外一个数组做桶，下标用来记录值，值用来记录该值的个数。

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        //桶排序
        //1.先定义一个桶,容量看题，最大是5000
        int[] bucket = new int[5001] ;
        //2.将数据进行桶排序
        for(int num : nums){
    
            //num 得到的是nums 里的值,bucket[nums]就是把数据作为下标，值作为数据出现的个数
            bucket[num]++;
        }
        //定义一个变量,待会就靠它取桶内的值了。 
        int j = 5000;
        //3. 开始放值，放1，3，5，7.....这些都是大值待的地方
        for(int i = 1; i < nums.length ; i +=2 ){
    
            //先找到桶内有意义的数据
            while(bucket[j] == 0){
    
                //这些都是无意义的数据，快速跳过，下标往回走
                j--;
            }
            //遇到数据了，开始赋值
            nums[i] = j;
            bucket[j]--;
        }
        //4. 放小数据，0,2,4,6,.....
        for(int i = 0 ; i < nums.length; i += 2){
    
            while(bucket[j] == 0){
    
                j--;
            }
            nums[i] = j;
            bucket[j]--;
        }


    }
}

建议

大家去做一做，虽然是中等难度的，但用对方法不难。