Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-sort
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment