Algorithm

LintCode/Wiggle Sort

Problem Summary

Given an unsorted array A, reorder it in-place such that A[0] <= A[1] >= A[2] <= A[3]…

Solution

We can sort the array then reorder it, of course. But it would take us O(N*logN) time. Let us consider whether we can solve this in linear time.

Suppose we iterate through the array and are currently at A[i], with A[0] to A[i-1] already “sorted”.
If i is odd and A[i] ≥ A[i-1] (or i is even and A[i] ≤ A[i-1]), then we can move on to A[i+1].
If not, we need to swap A[i] with A[i-1]. And this will not damage the work already done: if i is odd and A[i] < A[i-1], we also have A[i-2] ≥ A[i-1], so A[i-2] ≥ A[i-1] > A[i]. That is, the order between the (i-2)th number and (i-1)th number still maintains after the swap.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: nothing
     */
    void wiggleSort(vector<int> &nums) {
    	int n = nums.size();
    	for (int i = 0; i < n-1; ++i)
    		if ((i%2 && nums[i] < nums[i+1]) || (!(i%2) && nums[i] > nums[i+1]))
    			swap(nums[i],nums[i+1]);
    }
};