Java/Python O(n) time O(1) space solution 3+ lines


  • 16

    Python

    class Solution(object):
        def wiggleSort(self, nums):
            for i in xrange(1, len(nums)):
                if (i % 2) ^ (nums[i] > nums[i - 1]):
                    nums[i], nums[i - 1] = nums[i - 1], nums[i]
    
    
    # 125 / 125 test cases passed.
    # Status: Accepted
    # Runtime: 80 ms
    

    Java

    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            if ((i % 2 == 1) != (nums[i] > nums[i - 1])) {
                int cache = nums[i];
                nums[i] = nums[i-1];
                nums[i-1] = cache;
            }
        }
    }
    
    // 125 / 125 test cases passed.
    // Status: Accepted
    // Runtime: 1 ms

  • 0
    M

    It seems that OJ has been changed since your submission.
    I came up with the similar solution, but was rejected.
    For example:

    Input: [1,2,2,1,2,1,1,1,1,2,2,2]
    Output: [1,2,1,2,1,2,1,1,1,2,2,2]
    

    is now considered a wrong answer.


  • 0

    You must have confused this "280 Wiggle Sort" with "324 Wiggle Sort II", which do not allow a[i]=a[i+1].

    I have double checked these solutions, they still ac.


  • 0
    M

    Yes, you're right. Sorry, my bad!


Log in to reply
 

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