Wiggle Sort II

By | January 3, 2016
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

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[]: 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

  • Xiaoran Hu

    Haha, Peng, I am Xiaoran. Nice to see you here!

    • http://www.allenlipeng47.com peng li

      Thank you for finding me here. Welcome to read my blogs and we can discuss!