Leetcode Wiggle Sort II 求解！还没人给出过O(n)算法。。

大家好，求问一道题！这是leetcode上的Wiggle Sort II的原题：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].
这里不能像Wiggle Sort I 那样一次性遍历过数组只比较相邻的element。Discussion里面有人用先找中位数再swap的方法，复杂度是O(nlog(n))，而且过不了testcase [4, 5, 5, 6]。
现在OJ上貌似还没有O(n) time 和 O(1) space的方法。。。求大家一起提供思路啊！

先找中位数再swap,  算法是O(n),   找中位数， o(n) 就可以了

O(n)的思路和代码:
https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing
http://liveasatree.blogspot.com/2016/01/leetcode-wiggle-sort-ii.html

Related:
http://algobox.org/2015/12/31/wiggle-sort-ii/
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/en/35.0.md

1. class Solution {
   
2. public:
   
3.     int quickSelect(vector<int>& nums, int left, int right, int n) {
   
4.         // http://www.hrwhisper.me/leetcode-wiggle-sort-ii/
   
5.         if(left >= right) return nums[right];
   
6.         int start = left, end = right + 1;
   
7.         int mid = nums[left];
   
8.         while(start < end) {
   
9.             while(++start < right && nums[start] < mid) ;
   
10.             while(--end > left && nums[end] > mid) ;
    
11.             if(start >= end) break;
    
12.             swap(nums[start], nums[end]);
    
13.         }
    
14.         swap(nums[left], nums[end]);
    
15.         if(n == end - left + 1) return nums[end];
    
16.         else if(n < end - left + 1) return quickSelect(nums, left, end - 1, n);
    
17.         else return quickSelect(nums, end + 1, right, n - (end - left + 1));
    
18.     }
    
19. 
    
20.     int transformInd(int i, int len) {
    
21.         if(i < (len >> 1)) return i*2+1;
    
22.         else return (i - (len>>1))*2;
    
23.     }
    
24. 
    
25.     void wiggleSort(vector<int>& nums) {
    
26.         
    
27.         int len = nums.size();
    
28.         if(len < 2) return ;
    
29.         int median = quickSelect(nums, 0, len - 1, (len + 1) >> 1);
    
30.         int i = 0, j = 0, k = len - 1;
    
31.         while(i <= k) {
    
32.             int iT = transformInd(i, len), jT = transformInd(j, len), kT = transformInd(k, len);
    
33.             if(nums[iT] > median) {
    
34.                 swap(nums[iT], nums[jT]);
    
35.                 i++;
    
36.                 j++;
    
37.             }
    
38.             else if(nums[iT] < median) {
    
39.                 swap(nums[iT], nums[kT]);
    
40.                 k--;
    
41.             }
    
42.             else i++;
    
43.         }
    
44.     }
    
45. };

复制代码

c++抛砖引玉，看过楼上的原帖写的，transformInd的作用就相当于
    #define A(i) nums[(1+2*(i)) % (n|1)]// Index-rewiring.

eat0010 发表于 2016-2-25 01:28
找中位数可以O(n)？ 题目要求不能用额外memory的。

找中位数 O(n) 算法导轮上有

int transformInd(int i, int len) {
        if(i < (len >> 1)) return i*2+1;
        else return (i - (len>>1))*2;
    }
这个函数的意思是什么，不太明白，能不能解释一下

Ran2446541820 发表于 2016-2-28 17:30
int transformInd(int i, int len) {
        if(i < (len >> 1)) return i*2+1;
        else return (i ...

Index的mapping。如果是偶数长度array[0,1,2,3,4,5] --> [1,3,5,0,2,4]如果是奇数长度array[0,1,2,3,4,5,6]-->[1,3,5,0,2,4,6]其实就是(2*i + 1) % (length | 1)这个表达式。
Mapping了以后即可以把它当成sort color那样做了
参考这个博客：
http://bookshadow.com/weblog/2015/12/31/leetcode-wiggle-sort-ii/