324. Wiggle Sort II

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?

Solution:

Method 1: sort

Sort the array and put corresponding elements to wiggle position.

Need auxiliary array.

The time complexity is O(nlogn) and the space complexity is O(n).



Code:

public class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            int swap = nums[i];
            nums[i++] = nums[j];
            nums[j--] = swap;
        }
        int[] res = new int[nums.length];
        int m = nums.length | 1;
        for (i = 0; i < nums.length; i++) {
            res[(1 + i * 2) % m] = nums[i];
        }
        for (i = 0; i < res.length; i++) {
            nums[i] = res[i];
        }
    }
}

Method 2: 3-way partition and virtual indexing

Find median with O(n).

In-place exchange elements and put them to wiggle positions.

The time complexity is O(n) and the space complexity is O(1).

More explanation: Step by step explanation of index mapping in Java



Code:

public class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int median = findKthLargest(nums, n / 2 + 1);
        
        int left = 0, i = 0, right = n - 1;
        while (i <= right) {

            if (nums[mapIndex(i, n)] > median) {
                exch(nums, mapIndex(left++, n), mapIndex(i++, n));
            }
            else if (nums[mapIndex(i, n)] < median) {
                exch(nums, mapIndex(right--, n), mapIndex(i, n));
            }
            else {
                i++;
            }
        }
    }
    
    public int mapIndex(int index, int n) {
        return (1 + 2 * index) % (n | 1);
    }
    
    
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k - 1);
        
        return nums[k - 1];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int gt = lo;
        int lt = hi;
        int i = lo;
        
        while (i <= lt) {
            if (nums[i] > v) {
                exch(nums, gt++, i++);
            }
            else if (nums[i] < v) {
                exch(nums, lt--, i);
            }
            else {
                i++;
            }
        }
        
        if (gt < pos) {
            partition(nums, gt + 1, hi, pos);
        }
        if (gt > pos) {
            partition(nums, lo, gt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int swap = nums[i];
        nums[i] = nums[j];
        nums[j] = swap;
    }
}