324.md

324 Wiggle Sort II

Description

link

---

Solution

• waiting

---

Code

O(n) O(1)

class Solution:
    def wiggleSort(self, nums: 'List[int]') -> 'None':
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 1:
            return
        n = len(nums)

        # Index-rewiring.
        f = lambda i:(1+2*(i)) % (n|1)
        
        mid = self.quickselect(0, len(nums) - 1, nums, len(nums) // 2)
        
        # 3 way partition
        i, j, k = 0, 0, n-1

        while j <= k:
            if (nums[f(j)] > mid):
                nums[f(i)], nums[f(j)] = nums[f(j)], nums[f(i)]
                i += 1
                j += 1
            elif nums[f(j)] < mid:
                nums[f(j)], nums[f(k)] = nums[f(k)], nums[f(j)]
                k -= 1
            else:
                j += 1

        # print (nums)

    def quickselect(self, start, end, A, k):
        if start == end:
            return A[start]
            
        mid = self.partition(start, end, A)
        
        if mid == k:
            return A[k]
        elif mid > k:
            return self.quickselect(start, mid - 1, A, k)
        else:
            return self.quickselect(mid + 1, end, A, k)
        
    def partition(self, start, end, A):
        pivotIndex = random.randrange(start, end + 1)
        pivot = A[pivotIndex]
        A[end], A[pivotIndex] = A[pivotIndex], A[end]
        mid = start
        for i in range(start, end):
            if A[i] >= pivot:
                A[mid], A[i] = A[i], A[mid]
                mid += 1
        A[mid], A[end] = A[end], A[mid]
        return mid