classSolution: defwiggleSort(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ Cnums = sorted(nums) n = len(nums) for i inrange(1,len(nums),2): #奇数大于偶数位置 先放置奇数 n -= 1 nums[i] = Cnums[n] for i inrange(0,len(nums),2): #后放置偶数 因为中间的数据一部分在数组头,一部分在数组尾部,所以中间出现相等的情况就不会影响 n -= 1 nums[i] = Cnums[n] return nums
但是实际上不需要排序,因为只需要找到中位数即可,无需保证中位数的左右部分是顺序的。
首先找到中位数,准确说是第k个数(使用快速排序法)
使用三分法将数组分成三个部分小于中位数,等于中位数,大于中位数的部分
逆序穿插
这样时间复杂度为O(logn)+O(n),即为O(N)
解法二
总体函数
1 2 3 4 5 6 7 8 9
defwiggleSort(nums): n = len(nums) if n<=1: return nums k = (n+1)//2-1 mid_value = partition(nums, k, 0, n-1) three_way_partition(nums, mid_value) nums0 = nums.copy() for k inrange(n): nums[k] = nums0[(n+1)//2-1-k//2] if (not k%2) else nums0[(n-1)-k//2]
寻找中位数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
defpartition(nums, k, start, end): key = nums[start] left, right = start, end # print('nums={}, start={}, end={}'.format(nums,start,end)) # 循环中的不变量: left<right and nums[right]>=key and nums[left]<=key while left < right: while left < right and nums[right] >= key: right = right - 1 if left < right: nums[left],nums[right] = nums[right],nums[left] while left < right and nums[left] <= key: left = left + 1 if left < right: nums[left],nums[right] = nums[right],nums[left]
if left == k: return nums[left] elif left > k: return partition(nums, k, start, left-1) else: return partition(nums, k, left+1, end)