# ---
# title: 324. Wiggle Sort II
# id: problem324
# author: Tian Jun
# date: 2020-10-31
# difficulty: Medium
# categories: Sort
# link: <https://leetcode.com/problems/wiggle-sort-ii/description/>
# hidden: true
# ---
# 
# Given an unsorted array `nums`, reorder it such that `nums[0] < nums[1] >
# nums[2] < nums[3]...`.
# 
# **Example 1:**
# 
#     
#     
#     Input:nums = [1, 5, 1, 1, 6, 4]
#     Output: One possible answer is [1, 4, 1, 5, 1, 6].
# 
# **Example 2:**
# 
#     
#     
#     Input:nums = [1, 3, 2, 2, 3, 1]
#     Output: 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?
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
