Leetcode 324: Wiggle Sort II

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

You may assume the input array always has a valid answer.

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 5000
• It is guaranteed that there will be an answer for the given input nums.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

Problem Analysis:

First we can find the middle number that make half number of items in the array is less than or equal than it, also the half number of items greater than or equal than it.

Then we make them alternate in the array. Note that the items that equal to the middle number should not be adjacent with each other.

So as we use some tricky skill to put them layout in two boundaries

Solution

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        auto it = nums.begin() + nums.size() / 2;
        nth_element(nums.begin(), it, nums.end());
        int tmp = *it;
        #define A(i) nums[(1 + 2 * (i)) % (nums.size() | 1)]
        int i = 0, j = 0, k = nums.size() - 1;
        while (j <= k) {
            if (A(j) > tmp) swap(A(i++), A(j++));
            else if (A(j) < tmp) swap(A(k--), A(j));
            else ++j;
        }
    }
};

time complexity is O(n)

Space complexity is O(1)