4-lines O(n) C++


  • 35

    The final sorted nums needs to satisfy two conditions:

    1. If i is odd, then nums[i] >= nums[i - 1];
    2. If i is even, then nums[i] <= nums[i - 1].

    The code is just to fix the orderings of nums that do not satisfy 1 and 2.

    class Solution {
    public: 
        void wiggleSort(vector<int>& nums) {
            int n = nums.size();
            for (int i = 1; i < n; i++)
                if (((i & 1) && nums[i] < nums[i - 1]) || (!(i & 1) && nums[i] > nums[i - 1]))
                    swap(nums[i], nums[i - 1]);
        } 
    };

  • 13

    Good idea, just can be shorter:

    void wiggleSort(vector<int>& nums) {
        for (int i=1; i<nums.size(); ++i)
            if (i%2 == (nums[i-1] > nums[i]))
                swap(nums[i-1], nums[i]);
    }
    

    And here's a fun one:

    void wiggleSort(vector<int>& nums) {
        for (int i=1; i<nums.size(); ++i)
            swap(nums[i], nums[i - (i%2 ^ (nums[i-1] < nums[i]))]);
    }
    

  • 0

    Little correction for your explanation: The conditions are >= and <=, not > and <.


  • 0

    Oh yeah, I've updated it now. Thanks :-)


  • 0

    Hi, Stefan. Great thanks for these nice alternatives! Both versions are very interesting, especially the use of exclusive or ^ in the second one. I believe that you will have a one-liner if you use Ruby :-)


  • 0

    Hehe, I just tried Ruby, couldn't quite make a legitimate one-liner. Sometimes Ruby's automatic returning of the last value is trouble :-D


  • 1
    A

    Inspired by your solution. Python version

    def wiggleSort(self, nums):
        n = len(nums)
        for i in xrange(n-1):
            if (i % 2 == 0 and nums[i] > nums[i+1]) or (i % 2 == 1 and nums[i] < nums[i+1]):
                nums[i], nums[i+1] = nums[i+1], nums[i]

  • 0
    S

    I think the first version is the best with most readable.


  • 0
    J

    Works fine! great


  • 0
    R

    you guys are really genius. I'm still having problem understanding why this swap could hold the (in)equation, since every time you swap with the previous one, how could you make sure/prove that won't break the relatonship between i-2 and i-1 items after the swap?


  • 0
    N

    @robin8 I think it can be proved.


  • 0
    O

    Really impressive, but I think that the validity of this algorithm relies on the fact that when you fix the condition between nums[i] and nums[i-1], the relationship between nums[i-1] and nums[i-2] will NOT be affected.


  • 0
    W

    @robin8

    [... a, b, c, ...]

    if a > b > c
    then a > c
    so a > c < b is valid

    if a < b < c
    then a < c
    so a < c > b is valid


  • 0
    S

    @robin8 Hope its not too late:

    Proof of correctness:

    Let's use induction:

    Base case: only one element is processed, no constraints are violated.
    Step: if i % 2 == 0: If we do not swap anything at this step, the prefix remains valid. Otherwise, we have the following situation: a[i - 2] >= a[i - 1] > a[i]. When we make a swap, we can see that the constraints are not violated for the i - 2 and i - 1 elements, and the last position is fixed. For an odd i, the situation is similar.
    Credit: http://stackoverflow.com/questions/28567334/an-array-a1-2n-1-is-wiggly-if-a1-a2-a3-a4-a2n


Log in to reply
 

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