Short simple C++


  • 26
    void wiggleSort(vector<int>& nums) {
        vector<int> sorted(nums);
        sort(sorted.begin(), sorted.end());
        for (int i=nums.size()-1, j=0, k=i/2+1; i>=0; i--)
            nums[i] = sorted[i&1 ? k++ : j++];
    }
    

    Sort and then write the smaller half of the numbers on the even indexes and the larger half of the numbers on the odd indexes, both from the back. Example:

    Small half:    4 . 3 . 2 . 1 . 0 .
    Large half:    . 9 . 8 . 7 . 6 . 5
    ----------------------------------
    Together:      4 9 3 8 2 7 1 6 0 5
    

    So write nums from the back, interweaving sorted[0..4] (indexed by j) and sorted[5..9] (indexed by k).

    For more explanation/proof, see my equivalent Python solution.


  • 2
    L

    It's computationl complexity is O(n*log(n)) because of the using of sort, not O(n).


  • 4

    @lijianhui
    I know. So what? I never claimed it's O(n).


  • 0
    D

    I came up with exactly the same idea. But your codes are neater than mine (I used two "for" loops to put two sorted halfs back in nums). Good codes,


  • 0

    Well I'm sure two loops can be good as well. I'd just find it boring :-P


  • 3
    S

    I wanted to use exactly this idea when I was doing Wiggle Sort I, but then I dumped it since time complexity is O(nlogn) and space complexity is also not O(1)... And I hate the complicated solution to this problem... Oh Jesus


  • 0
    E

    nice and clean code


  • 0
    A
    This post is deleted!

  • 4
    J

    can you explain why you modify elements from the end instead from the begin?


  • 1
    F

    @StefanPochmann said in Short simple C++:

    for (int i=nums.size()-1, j=0, k=i/2+1; i>=0; i--)
    nums[i] = sorted[i&1 ? k++ : j++];

    I got it now. didn't find @StefanPochmann 's explain link earlier.
    For some guys make the same mistake as mine, here's a head up.
    Stefan's insert order makes the middle consecutive two same number M.
    Large half M go way back to end but small half M go front. Very clever!

    As a tip here to help anyone has the same problem as mine, go check Stefan's link up there.

    /////
    previous post below
    ////
    Hello, I take the same idea as yours instead of putting value from i==size-1, I start i from 0.
    It got Wrong answer.
    Input:
    [4,5,5,6]
    Output:
    [4,5,5,6]
    Expected:
    [5,6,4,5]

    Does it mean it better assigning value as your order from end to begin? And may I ask what make you choose this order? Thank you!

    class Solution {
    public:
        void wiggleSort(vector<int>& nums) {
            vector<int> sorted(nums);
            sort(sorted.begin(), sorted.end());
            //len=1 0
            //1
            //len=2 0(1)
            //
            //len=4 01(2)3
            //
            //len=5 012(3)4
            //(len+1)/2=3
            //len=6 012(3)45
            //(len+1)/2=3
            //len=7 0123(4)56
            //len+1)/2=4
            
            //[4,5,5,6]
            /*
            for (int i=nums.size()-1{3}, j=0, k=i/2+1{2}; i>=0; i--){
                nums[i] = sorted[i&1 ? k++ : j++];
            }*/
            //[  [1]5 ,[3]6 ,[0]4, [2]5 ]
            /*
            for(int i=(nums.size()-1), j=0, k=(nums.size()+1)/2;i>=0;i--){
                //cout<<(i&1)<<"j="<<j<<"k="<<k<<endl;
                nums[i]= ((i&1)==0)? sorted[j++] : sorted[k++];
                //cout<<(i&1)<<"j="<<j<<"k="<<k<<endl;
            }*/
            for(int i=0, j=0, k=(nums.size()+1)/2;i<nums.size();i++){
                nums[i]= ((i&1)==0)? sorted[j++] : sorted[k++];
            }
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.