Wiggle Sort II

题目地址：
https://leetcode.com/problems/wiggle-sort-ii/description/

题目：

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

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], 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?

解题思路：
link：https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java


代码：

 public static void main(String[] args){
        WiggleSort2 wiggleSort2 = new WiggleSort2();
//        int[] nums = {1,5,1,1,6,4};        int[] nums = {1,1,2,1,2,2,1};
        wiggleSort2.wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void wiggleSort(int[] nums) {
        if(nums == null || nums.length <= 1){
            return;
        }
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        int median = findKthLargest(nums, (nums.length) / 2);
        for(int i = 0; i <= right; i++){
            int currIndex = findIndex(i, len);
            if(nums[currIndex] > median){
                swap(nums, findIndex(left++, len), findIndex(i, len));
            }
            else if(nums[currIndex] < median){
                swap(nums, findIndex(right--, len), findIndex(i--, len));
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private int findIndex(int i, int len) {
        if(len % 2 == 0){
            return (2 * i + 1) % (len + 1);
        }
        else{
            return (2 * i + 1) % len;
        }
    }

    // find the kth largest in the array    private int findKthLargest(int[] nums, int k){
        k = nums.length - k + 1;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        for(int i = 0; i < nums.length; i++){
            minHeap.offer(nums[i]);
        }
        int len = nums.length;
        for(int i = 0; i <= len - k - 1; i++){
            minHeap.poll();
        }
        return minHeap.poll();
    }