# 324. Wiggle Sort II / Medium

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]

## Comstraints

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

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

# Solution 1: Sort and Partition

## 效能

### Complexity

• Time Complexity: O(NlogN)
• Space Complexity: O(N)

### LeetCode Result

• Runtime: 16 ms
• Memory Usage: 17.7 MB

# Solution 2: Quickselect + DNF (Follow Up)

## 思路

`[1,5,1,1,6,4]`為例，`[1,6,1,5,1,4]``[1,4,1,5,1,6]`都是可以接受的答案。

Related Problem:

`#define A(i) nums[(1 + 2 * i) % (n | 1)]`

## 效能

### Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

### LeetCode Result

• Runtime: 11 ms
• Memory Usage: 17.4 MB