方法一：排序后+翻轉(zhuǎn)子數(shù)組
將數(shù)組排序后讼油，分割成兩個(gè)數(shù)組a棘街、b，a的長(zhǎng)度等于b或者大1硕勿。然后將a、b兩個(gè)數(shù)組的元素輪流插入到原數(shù)組中。但是舟误，在中位數(shù)元素出現(xiàn)超過次數(shù)大于半數(shù)時(shí)，會(huì)出現(xiàn)兩個(gè)中位數(shù)排在一起姻乓，不滿足本題嚴(yán)格大于小于的要求嵌溢。解決方法是將a、b翻轉(zhuǎn)后在進(jìn)行輪流插入蹋岩。
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
arr = sorted(nums)
m = (len(nums)+1) // 2
arr1 = arr[:m][::-1]
arr2 = arr[m:][::-1]
for i in range(len(arr1)):
nums[2*i] = arr1[i]
for i in range(len(arr2)):
nums[2*i+1] = arr2[i]
方法二：快速選擇 + 3-way-partition
使用快速排序中的partition函數(shù)赖草，來找到中位數(shù)的值，然后使用三路partition方法對(duì)nums數(shù)組進(jìn)行劃分剪个，形成四個(gè)區(qū)間秧骑，
都小于
，
都等于
，
為未處理區(qū)間乎折，
都大于
绒疗。遍歷時(shí)移動(dòng)
，當(dāng)
時(shí)結(jié)束循環(huán)骂澄。
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# midval = self.partition(nums, 0, len(nums)-1, len(nums)//2)
t = nums.copy()
midval = sorted(t)[len(t)//2]
# print(midval)
# [0, i-1], [i, j-1] [j, k-1] , [k,n-1]
i = 0
j = 0
k = len(nums)
while j < k:
if nums[j] > midval:
k -= 1
nums[j], nums[k] = nums[k], nums[j]
elif nums[j] < midval:
nums[j], nums[i] = nums[i], nums[j]
i += 1
j += 1
else:
j += 1
mid = (len(nums)+1)//2
arr1 = nums[:mid][::-1]
arr2 = nums[mid:][::-1]
for i in range(len(arr1)):
nums[2*i] = arr1[i]
for i in range(len(arr2)):
nums[2*i+1] = arr2[i]
def partition(self, nums, l, r, t):
m = random.randint(l,r)
nums[r], nums[m] = nums[m], nums[r]
#[l, i-1], [i, k], [k+1, r]
i = l
pivot = nums[r]
for k in range(l, r):
if nums[k] <= pivot:
nums[i], nums[k] = nums[k], nums[i]
i += 1
nums[i], nums[r] = nums[r], nums[i]
# print("nums:{}, l:{}, r:{}, m:{}".format( nums, l, r, i))
if i == t:
return nums[i]
elif i < t:
return self.partition(nums, i+1, r, t)
else:
return self.partition(nums, l, i-1, t)
