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?

 

The virtual index idea in the post https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing
is very brilliant! However, it takes me a while to understand why and how it works. There is no ‘nth_element’ in Java, but you can use ‘findKthLargest’ function from “https://leetcode.com/problems/kth-largest-element-in-an-array/” to get the median element in average O(n) time and O(1) space.

Assume your original array is {6,13,5,4,5,2}. After you get median element, the ‘nums’ is partially sorted such that the first half is larger or equal to the median, the second half is smaller or equal to the median, i.e

In the post https://leetcode.com/discuss/76965/3-lines-python-with-explanation-proof, we have learned that , to get wiggle sort, you want to put the number in the following way such that

(1) elements smaller than the ‘median’ are put into the last even slots

(2) elements larger than the ‘median’ are put into the first odd slots

(3) the medians are put into the remaining slots.

M – Median, S-Small, L-Large. In this example, we want to put {13, 6, 5} in index 1,3,5 and {5,4,2} in index {0,2,4}

The index mapping, (1 + 2*index) % (n | 1) combined with ‘Color sort’, will do the job.

After selecting the median element, which is 5 in this example, we continue as the following

The code is the following:

The code is the following:

Another method uses more space (O(n) extra space,O(n) time) and it’s easier to understand.