This one is from leetcode: https://leetcode.com/problems/wiggle-sort-ii/
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]...
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
An old similar problem is wave sort. But in wave sort, it doesn’t has duplicate elements, which we can do it in linear time, O(1) extra space easily. link But for this problem, the difference is that it contains duplicate elements, which make it harder.
Ok, the solution is like below:
1. Sort array in descending order.
2. Put smaller elements into small[].
3. Put larger elements into large[].
4. Merge small[] and large[]: Small is more element. so put small first.(Or in another word put small in even position, put large in odd position)
For example nums = [1, 2, 3, 4, 5].
Step 1, arr = [5, 4, 3, 2, 1]
Step 2, small = [3, 2, 1]
Step 3, large = [5, 4]
Step 4, arr = [3, 5, 2, 4, 1]
Another example nums = [4, 5, 5, 6]
Step 1, arr = [6, 5, 5, 4]
Step 2, small = [5, 4]
Step 3, large = [6, 5]
Step 4, arr = [5, 6, 5, 4]
check my code on github: link