Leetcode:324. 摆动排序 II

题目描述

给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

示例 1:

输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]

示例 2:

输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]

说明:

你可以假设所有输入都会得到有效的结果。

进阶:

你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

思路

思路1

直接使用排序加取后一半位置进行插入到合适的位置，需要注意需要新建一个前半排序和后半排序后的空间，不然由于交换不能到合适的位置(或者用一个map指示排序后每个元素应该在的位置),同时还需要注意最中间的元素等于(nums.length + 1) /2的情况，所以需要能够前后排序空间都逆序，使其中间元素不在一起即在排序时不产生等号

思路2

不使用排序而直接使用三partition将数组形成小于中位数的数+中数+大于中位数的数，然后利用两个数组（中间位置之前和之后的数组）逆序，最后根据两个数组得到最后的结果

思路3

将两个数组换位虚地址

代码

代码1

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length == 0){
            return;
        }
        Arrays.sort(nums);
        int mid = (nums.length + 1) / 2;
        reverse(nums, 0, mid - 1);
        reverse(nums, mid, nums.length - 1);
        int[] smallNums = new int[mid];
        int[] bigNums = new int[nums.length - mid];
        for(int i = 0; i < nums.length; i++){
            if (i <= mid - 1){
                smallNums[i] = nums[i];
            }else{
                bigNums[i - mid] = nums[i];
            }
        }
        for(int i = 0; i < nums.length; i++){
            if (i % 2 == 0){
                nums[i] = smallNums[i / 2];
            }else{
                nums[i] = bigNums[i / 2];
            }
        }
    }
    
    private void reverse(int[] nums,int start,int end){
        while (start < end){
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
    
}

代码2

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1){
            return;
        }
        int mid = (nums.length + 1) / 2;
        if (nums.length > 1){
            quickSelect(nums, 0, nums.length - 1, mid, false);
        }
        int midNum = nums[mid];
        int midIndex = 0, k = nums.length - 1, iterIndex =0;
        while (midIndex < k){
            if (nums[midIndex] > midNum){
                swap(nums, midIndex, k);
                k --;
            }else if(nums[midIndex] < midNum){
                swap(nums, midIndex, iterIndex);
                midIndex++;
                iterIndex++;
            }else{
                midIndex++;
            }
        }
        int[] smallNums = new int[mid];
        int[] bigNums = new int[nums.length - mid];
        for(int i = 0; i < nums.length; i++){
            if (i < mid){
                smallNums[i] = nums[mid - 1 - i];
            }else{
                bigNums[i - mid] = nums[nums.length - 1 - (i - mid)];
            }
        }
        for(int i = 0; i < nums.length; i++){
            if (i % 2 == 0){
                nums[i] =  smallNums[i / 2];
            }else{
                nums[i] = bigNums[i / 2];
            }
        }
    }
    
    private void quickSelect(int[] nums,int start,int end,int k, boolean reverse){
        int getIndex = getPartition(nums, start, end, reverse);
        while (getIndex != k){
            if (getIndex > k){
                getIndex = getPartition(nums, start, getIndex - 1, reverse);
            }
            if (getIndex < k){
                getIndex = getPartition(nums, getIndex + 1, end, reverse);
            }
        }
    }
    
    private int getPartition(int[] nums, int start, int end, boolean reverse){
        int getNum = nums[start];
        int getIndex = start;
        swap(nums, start, end);
        for(int i = start; i < end; i++){
            if ((!reverse && nums[i] < getNum) || (reverse && nums[i] > getNum)){
                swap(nums, getIndex++, i);
            }
        }
        swap(nums, getIndex, end);
        return getIndex;
    }
    
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
}

复杂度分析

思路1时间复杂度

$O(nlogn)$考虑平均情况

思路1空间复杂度

$O(n)$

思路2时间复杂度

$O(n)$考虑平均情况

思路2空间复杂度

$O(n)$

思路3时间复杂度

$O(n)$考虑平均情况

思路3空间复杂度

$O(1)$

参考文献

• Leetcode:324题解