Python solution with detailed explanation


  • 0
    G

    Solution

    Wiggle Sort https://leetcode.com/problems/wiggle-sort/

    Solution 1: Sorting

    • Just sort the array and swap adjacent elements
    class Solution(object):
        def wiggleSort(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            nums.sort()
            i = 1
            while i+1 < len(nums):
                nums[i], nums[i+1] = nums[i+1], nums[i]
                i += 2
            return
    

    Solution 2: O(N) solution in one pass

    • Assume a1,a2,..a[n-1],a[n] is already wiggle sorted.
    • Now we have a[n+1] and we want a[n]<=a[n+1]. This means a[n-1] >=a[n]
    • Case 1: a[n] <= a[n+1] - All conditions are satisfied
    • Case 2: a[n] > a[n+1]
      • Swap and this leads to a[n-1] ? a[n+1] < a[n]
      • What is ?. a[n-1] >=a[n]. a[n] > a[n+1]. This means a[n-1]>a[n+1]
      • Hence we have a[n-1] > a[n+1] < a[n]
    class Solution(object):
        def wiggleSort(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            i, less = 0, True
            while i+1 < len(nums):
                if less:
                    if nums[i+1] < nums[i]:
                        nums[i],nums[i+1] = nums[i+1], nums[i]
                else:
                    if nums[i+1] > nums[i]:
                        nums[i],nums[i+1] = nums[i+1], nums[i]
                i, less = i+1, not less
            return
    

Log in to reply
 

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