Wiggle Sort II 507

Question

Given an unsorted array nums, reorder it such that

nums[0] < nums[1] > nums[2] < nums[3]....

Notice

You may assume all input has valid answer.

Example

Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].

Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Challenge

Can you do it in O(n) time and/or in-place with O(1) extra space?

Solution

这道题其实就是要找一个中间值，比中间值小的插入到偶数位上，比中间值大的插入到奇数位上。

1. 用quick select寻找中间值（即能平分nums中所有元素的元素的值）

2. 将ans的值全部设为中间值，遍历数组nums，将遇到的数和中间值比较，间隔地插入ans中

3. 若原数组长度为偶数，则为小->大->小。。。->大的形式，小的数从后往前(len - 2)寻找位置插入，大的数从前往后(1)寻找位置插入

   若原数组长度为奇数，则为大->小->大。。。->小的形式，小的数从前往后(0)寻找位置插入，大的数从后往前(len - 2)寻找位置插入

代码如下：

public class Solution {
    /**
     * @param nums a list of integer
     * @return void
     */
    public void wiggleSort(int[] nums) {
        // Write your code here
        if(nums == null || nums.length <= 1){
            return;
        }

        int[] temp = Arrays.copyOfRange(nums, 0, nums.length);
        int avg = partition(temp, 0, nums.length - 1, nums.length / 2);
        int[] ans = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            ans[i] = avg;
        }

        int l, r;
        if(nums.length % 2 == 0){
            l = nums.length - 2;
            r = 1;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] < avg){
                    ans[l] = nums[i];
                    l -= 2;
                }else if(nums[i] > avg){
                    ans[r] = nums[i];
                    r += 2;
                }
            }
        }else{
            l = 0;
            r = nums.length - 2;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] < avg){
                    ans[l] = nums[i];
                    l += 2;
                }else if(nums[i] > avg){
                    ans[r] = nums[i];
                    r -= 2;
                }
            }
        }

        for(int i = 0; i < nums.length; i++){
            nums[i] = ans[i];
        }
    }

    private int partition(int[] temp, int left, int right, int rank){
        int l = left;
        int r = right;
        int now = temp[left];
        while(l < r){
            while(l < r && temp[r] >= now){
                r--;
            }
            temp[l] = temp[r];
            while(l < r && temp[l] <= now){
                l++;
            }
            temp[r] = temp[l];
        }
        temp[l] = now;

        if(l - left < rank){
            return partition(temp, l + 1, right, rank - (l - left) - 1);
        }else if(l - left > rank){
            return partition(temp, left, r - 1, rank);
        }
        return now;
    }
}