- 标签:数组、分治、快速选择、排序
- 难度:中等
给你一个整数数组 nums
。
要求:将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3] ...
的顺序。可以假设所有输入数组都可以得到满足题目要求的结果。
注意:
-
$1 \le nums.length \le 5 * 10^4$ 。 -
$0 \le nums[i] \le 5000$ 。
num[i]
的取值在 [0, 5000]
。所以我们可以用桶排序算法将排序算法的时间复杂度降到
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
buckets = [0 for _ in range(5010)]
for num in nums:
buckets[num] += 1
size = len(nums)
big = size - 2 if (size & 1) == 1 else size - 1
small = size - 1 if (size & 1) == 1 else size - 2
index = 5000
for i in range(1, big + 1, 2):
while buckets[index] == 0:
index -= 1
nums[i] = index
buckets[index] -= 1
for i in range(0, small + 1, 2):
while buckets[index] == 0:
index -= 1
nums[i] = index
buckets[index] -= 1