Leetcode #324. Wiggle Sort II

[yokostan]

This solution is so good and beats 100%, almost feel like cheating:

class Solution {
    public void wiggleSort(int[] nums) {
        int[] copy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(copy);

        int n = nums.length;
        int left = (n + 1) / 2 - 1; // median index
        int right = n - 1; // largest value index
        for (int i = 0; i < nums.length; i++)
        {   // copy large values on odd indexes
            if(i%2==1){
                nums[i] = copy[right];
                right--;
            } else{ // copy values decremeting from median on even indexes
                nums[i] = copy[left];
                left--;
            }
        }
    }
}

Make a copy of the array and sort it to two parts. But the sorting is actually O(nlogn)

Another O(n) solution, while its actually running time is longer:

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null) return ;
        int n = nums.length;
        int median = findKthLargest(nums, (nums.length + 1) / 2);

        int left = 0, right = n - 1, i = 0;

        while (i <= right) {
            if (nums[newIndex(i,n)] > median) {
                swap(nums, newIndex(left++,n), newIndex(i++,n));
            }
            else if (nums[newIndex(i,n)] < median) {
                swap(nums, newIndex(right--,n), newIndex(i,n));
            }
            else {
                i++;
            }
        }
    }

    public int newIndex(int index, int n) {
        return (1 + 2 * index) % (n | 1);
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

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

    public int quickSelect(int[] a, int lo, int hi, int k) {
        int i = lo, j = hi, pivot = a[hi];
        while (i < j) {
            if (a[i++] > pivot) swap(a, --i, --j);
        }
        swap(a, i, hi);

        int m = i - lo + 1;
        if (m == k) return a[i];
        else if (m > k) return quickSelect(a, lo, i - 1, k);
        else return quickSelect(a, i + 1, hi, k - m);
    }
}

[yokostan]

reference for 2nd solution: https://leetcode.com/problems/wiggle-sort-ii/discuss/77682/Step-by-step-explanation-of-index-mapping-in-Java And for ``newIndex'' from @kai99 This is to explain why mapped index formula is (1 + 2*index) % (n | 1)

Notice that by placing the median in it's place in the array we divided the array in 3 chunks: all numbers less than median are in one side, all numbers larger than median are on the other side, median is in the dead center of the array.

We want to place any a group of numbers (larger than median) in odd slots, and another group of numbers (smaller than median) in even slots. So all numbers on left of the median < n / 2 should be in odd slots, all numbers on right of the median > n / 2 should go into even slots (remember that median is its correct place at n / 2)

PS: I'm ignoring the discussion of odd/even array length for simplicity.

So let's think about the first group in the odd slots, all numbers is the left side of the array should go into these odd slots. What's the formula for it? Naturally it would be: (1 + 2 x index) % n

All these indexes are less than n / 2 so multiplying by 2 and add 1 (to make them go to odd place) and then mod by n will always guarantee that they are less than n.

Original Index => Mapped Index 0 => (1 + 2 x 0) % 6 = 1 % 6 = 1 1 => (1 + 2 x 1) % 6 = 3 % 6 = 3 2 => (1 + 2 x 2) % 6 = 5 % 6 = 5

These are what's less than median, if we continue this with indexes 3, 4, 5 we will cycle again: 3 => (1 + 2 x 3) % 6 = 7 % 6 = 1 4 => (1 + 2 x 4) % 6 = 9 % 6 = 3 5 => (1 + 2 x 5) % 6 = 11 % 6 = 5

and we don't want that, so for indexes larger than n/2 we want them to be even, (n|1) does that exactly. What n|1 does it that it gets the next odd number to n if it was even if n = 6 for example 110 | 1 = 111 = 7 if n = 7 for example 111 | 1 = 111 = 7

and this is what we want, instead of cycling the odd numbers again we want them to be even, and odd % odd number is even so updating the formula to : (1 + 2*index) % (n | 1)

Then we have: 3 => (1 + 2 x 3) % 7 = 7 % 7 = 0 4 => (1 + 2 x 4) % 7 = 9 % 7 = 2 5 => (1 + 2 x 5) % 7 = 11 % 7 = 4