Python solution with minheap


  • 0
    L

    This solution use minheap.

    class Solution(object):
        def wiggleSort(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            import heapq as hq
    
            hq.heapify(nums)
            s_length = len(nums) / 2
            l_length = len(nums) / 2
            if len(nums) % 2 == 1:
                s_length += 1
    
            n_smallest_heap = hq.nsmallest(s_length, nums)
            n_largest_heap = hq.nlargest(l_length, nums)
    
            for i in xrange(l_length):
                nums[2*i] = n_smallest_heap[-1*(i+1)]
                nums[2*i+1] = n_largest_heap[i]
    
            if s_length > l_length:
                nums[s_length+l_length-1] = n_smallest_heap[0]
    

  • 0
    L

    Heapify is O(nlogn)


Log in to reply
 

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