Python | Leetcode Python题解之第324题摆动排序II

题目：

题解：

def quickSelect(a: List[int], k: int) -> int:seed(datetime.datetime.now())shuffle(a)l, r = 0, len(a) - 1while l < r:pivot = a[l]i, j = l, r + 1while True:i += 1while i < r and a[i] < pivot:i += 1j -= 1while j > l and a[j] > pivot:j -= 1if i >= j:breaka[i], a[j] = a[j], a[i]a[l], a[j] = a[j], pivotif j == k:breakif j < k:l = j + 1else:r = j - 1return a[k]class Solution:def wiggleSort(self, nums: List[int]) -> None:n = len(nums)x = (n + 1) // 2target = quickSelect(nums, x - 1)transAddress = lambda i: (2 * n - 2 * i - 1) % (n | 1)k, i, j = 0, 0, n - 1while k <= j:tk = transAddress(k)if nums[tk] > target:while j > k and nums[transAddress(j)] > target:j -= 1tj = transAddress(j)nums[tk], nums[tj] = nums[tj], nums[tk]j -= 1if nums[tk] < target:ti = transAddress(i)nums[tk], nums[ti] = nums[ti], nums[tk]i += 1k += 1