From: http://www.mitbbs.com/article_t/JobHunting/32911043.html

Given an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.

eg:
[1,4,5,2,3]

o/p:
[1,4,2,5,3]

so, 3 > 2 > 1,  and 5 > 4
有没有o(n) 解法

---

Solution:

Do a quick_select(n/2), O(n) time. Then all the elements in the first half are smaller than the second half. Then construct new array where odd positions are from first half, and even positions are from second half.