leetcode-sort

280. Wiggle Sort.py

class Solution:
    """
    [3,5,2,1,6,4]
     n = 6
     mid = 3
     [1,2,3,5,6,4]
        i     j
     i = mid-1 if n%2==0
     tmp_arr = [3,4,2,6,1,5]
     在把tmp_arr猜回array
    """
    def wiggleSort(self, nums: List[int]) -> None:
        n = len(nums)        
        if n == 0:
            return 
        mid = n // 2 
        start, end = 0, len(nums)-1
        threshold = self.quickselect(nums, start, end, mid)       
        l, r = self.partition(nums, 0, len(nums)-1, threshold)
        # fill temporary array
        arr = [0 for _ in range(n)]
        i = n // 2 - 1 if n % 2 == 0 else n//2
        j = n - 1
        for idx in range(n):
            if idx % 2 == 0:
                arr[idx] = nums[i]
                i -= 1
            else:
                arr[idx] = nums[j]
                j -= 1
        # final step to modify array
        for i in range(n):
            nums[i] = arr[i]
                
    def quickselect(self, nums, s, e, k):
        pivot = nums[s+(e-s)//2]
        
        l, r = self.partition(nums, s, e, pivot)
        if l<=k<=r:
            return nums[k]
        elif k < l:
            return self.quickselect(nums, s, l-1, k)
        elif k > r:
            return self.quickselect(nums, r+1, e, k)
            
    def partition(self, a, l, r, t):
        m = l
        while m <= r:
            if a[m] > t:
                a[r], a[m] = a[m], a[r]
                r-=1
            elif a[m] < t:
                a[l], a[m] = a[m], a[l]
                l+=1
                m+=1
            else:
                m+=1
        return l, r