# 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)