Python solution with quickselect


  • 0
    Z
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums) <= 1: return
        
        def quickSelect(start, end):
            pivot = nums[end]
            i = start
            for j in range(start, end):
                if nums[j] <= pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
            nums[i], nums[end] = nums[end], nums[i]
            return i
        
        start, end, mid = 0, len(nums)-1, 0
        while True:
            mid = quickSelect(start, end)
            if mid == (len(nums)+1)/2:
                break
            elif mid > (len(nums)+1)/2:
                end = mid-1
            else:
                start = mid+1
        
        if mid % 2 == 1:
            i, j = 1, mid+1
        else:
            i, j = 1, mid
        while j < len(nums):
            nums[i], nums[j] = nums[j], nums[i]
            i, j = i+2, j+2

Log in to reply
 

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