WiggleSortII.java

import java.util.Arrays;

/**
 * TestCase
 * [1,2,2,1,2,1,1,1,1,2,2,2]
 */
public class WiggleSortII {

    // 时间复杂度O(nlgn)，空间复杂度O(n)
    // 先排序，然后从中间分成两半，先取前面一半的末尾，再取后半的末尾，再取前半的倒数第二个，再取后半倒数第二个，依次类似
    // 注意当个数为奇数时，中间那个要分到前面一半中
    public void wiggleSort2(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int n = nums.length, j = (n - 1) / 2, k = n - 1;
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i % 2 == 0 ? arr[j--] : arr[k--];
        }
    }

    /**
     * 这个解法的核心思想如下：
     * 用partition法将数组分为三波，左边一波为大于median的记为L，中间一波为median记为M，右边一波为小于median的记为S，每一波内顺序都无所谓
     * 将L从左到右依次放在奇数位上，将S从右到左依次放在偶数位上，多余的空填M。
     * 最终结果类似如下：
     * M L S L S M
     * M L S L S
     * 只要这样交叉放着就能符合wiggle
     * 直观的做法是另外开辟一个空间来放wiggle结果
     * 如果要求不开辟空间，则只能用坐标映射了
     * 类似的可以参考sort colors和find kth largest element
     */
    // 时间复杂度O(n)，空间复杂度O(l)
    public void wiggleSort(int[] nums) {
        int len = nums.length;
        int median = findKthLargest(nums, (len + 1) / 2);
        for (int left = 0, right = len - 1, i = 0; i <= right; ) {
            if (nums[newIndex(i, len)] > median) {
                swap(nums, newIndex(left++, len), newIndex(i++, len));
            } else if (nums[newIndex(i, len)] < median) {
                swap(nums, newIndex(right--, len), newIndex(i, len));
            } else {
                i++;
            }
        }
    }

    /**
     * 将数组分为两半，后面一半的个数大于等于前面的一半
     * 先取后面一半的第一个，再取前面一半的第一个
     * 再取后面一半的第二个，再取前面一半的第二个
     * 依次类推，得到一个映射关系
     */
    private int newIndex(int index, int n) {
        int ret = (1 + 2 * index) % (n | 1);
//        System.out.println(String.format("newIndex for %d, %d = %d", index, n, ret));
        return ret;
    }

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

    public int findKthLargest(int[] nums, int k) {
        return nums[findKthLargest(nums, 0, nums.length - 1, k)];
    }

    public int findKthLargest(int[] nums, int start, int end, int k) {
        int pivot = partition(nums, start, end);

        int rank = end - pivot + 1;

        if (rank == k) {
            return pivot;
        } else if (rank > k) {
            return findKthLargest(nums, pivot + 1, end, k);
        } else {
            return findKthLargest(nums, start, pivot - 1, k - rank);
        }
    }

    public int partition(int[] nums, int start, int end) {
        int pivot = nums[end], left = start;

        for (int i = start; i < end; i++) {
            if (nums[i] <= pivot) {
                swap(nums, left++, i);
            }
        }

        swap(nums, left, end);

        return left;
    }
}