Question:

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?

Thinking:

Firstly, we get information from the question is that we should divide all the elements into two groups. One is smaller ones, and the other is greater ones. Then we need to get the median to group them.

So we need the method called quickselect which is used in the kth largest element to get the median. Then rewire the element to new index which use (1+2(i)) % (n|1). It(A(i) = nums[(1+2(i)) % (n|1)]) means:

If the length of array is 10, then

Accessing A(0) actually accesses nums[1].
Accessing A(1) actually accesses nums[3].
Accessing A(2) actually accesses nums[5].
Accessing A(3) actually accesses nums[7].
Accessing A(4) actually accesses nums[9].
Accessing A(5) actually accesses nums[0].
Accessing A(6) actually accesses nums[2].
Accessing A(7) actually accesses nums[4].
Accessing A(8) actually accesses nums[6].
Accessing A(9) actually accesses nums[8].

We firstly put ones greater than median, then median, finally smaller than median. We’ll get the result.

There are some details to notice:

1. In the rewiring process, we need to distinguish whether the length of the array is odd or even. Use the (n|1).
2. In the 3 way partition process, when move larger element to the head, we don’t need to check it again. Because the element move from the head to the current position is checked before. On the other hand, the element which is moved from the current position to tail, we need to check it again.

Solution:

public void wiggleSort(int[] nums) {
    int len = nums.length;
    if (len < 2)    return;

    quickselect(nums, (len-1)/2);
    int mid = nums[(len-1)/2];

    int i = 0, j = len - 1, cur = 0;

    while (cur <= j) {
        if (nums[(2*cur+1)%(len|1)] > mid)
            swap(nums, (2*(cur++)+1)%(len|1), (2*(i++)+1)%(len|1));
        else if (nums[(2*cur+1)%(len|1)] < mid)    
            swap(nums, (2*(cur)+1)%(len|1), (2*(j--)+1)%(len|1));
        else    
            cur++;
    }
}

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

private void quickselect(int[] nums, int n) {
    int low = 0, high = nums.length-1;

    while (true) {
        int i = partition(nums, low, high);
        if (i == n)    return;
        else if (i < n) low = i + 1;
        else    high = i - 1;
    }
}

private int partition (int[] nums, int left, int right) {
    int pivot = nums[left];
    int storeIndex = left;
    nums[left] = nums[right];
    for (int i = left; i < right; i++) {
        if (nums[i] <= pivot)
            swap(nums, storeIndex++, i);
    }
    nums[right] = nums[storeIndex];
    nums[storeIndex] = pivot;

    return storeIndex;
}

Reference: https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing