(TBD)324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

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

Solution

這題靠北難，已經看了解答還是不太理解。

大致上的理解是透過kth largest Element那裏得到的方法找到中間值(medium value), 同時array會被切分成兩大部分，左半邊是大於medium value,右半邊是小於medium value。

然後把會想把左半邊的跟右半邊的交叉擺放，就可以得到wiggle array.

把左半邊的都從依序擺放到所有的奇數位置，右半邊的都擺放到偶數位置。即可求解。

重新計算位置的方法是 (1+2*i)%(n|1) , 其中i是本來的位置，n是array的大小。

public void wiggleSort(int[] nums) {
    int n = nums.length, m = (n + 1) >> 1;
    int median = findKthLargest(nums, m);
    
    //TOBEDONE: 這裡的轉換還是不太懂
    for (int i = 0, j = 0, k = n - 1; j <= k;) {
        if (nums[A(j, n)] > median) {
            swap(nums, A(i++, n), A(j++, n));
        } else if (nums[A(j, n)] < median) {
            swap(nums, A(j, n), A(k--, n));
        } else {
            j++;
        }
    }
}

private int getNewIndex(int i, int n) {
    return (2 * i + 1) % (n | 1);
}

 public int findKthLargest(int[] nums, int k) {
        shuffle(nums);
        return quickSelect(nums, 0, nums.length-1,  k-1);
    }
    
    public void shuffle(int[] nums){
        for(int i = 0 ; i < nums.length; i++){
            swap(nums, i, (int)(Math.random()*(nums.length-1)));
        }
    }
    
    public int quickSelect(int[] nums, int start, int end, int k){
        int left = start;
        int pivot = nums[end];
        for(int i = start; i < end; i++){
            if(pivot < nums[i]){
                swap(nums, left, i);
                left++;
            }
        }
        swap(nums, left, end);
        if(left == k){
            return pivot;
        }
        else if (left < k){
            //k is on the right ride
            return quickSelect(nums, left+1, end, k);
        }
        else {
            //k is on the left ride
            return quickSelect(nums, start, left-1, k);
        }
    }
    
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }