203 - 324 摆动排序2
题目
给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 1:
输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
输入: nums = [1, 3, 2, 2, 3, 1] 输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明: 你可以假设所有输入都会得到有效的结果。
进阶: 你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗?
解答
感觉是要把数组分成两部分,小的和大的,全部小的要小于全部大的。然后两两插入即可。
排序
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
s = sorted(nums, reverse=True)
nums[1::2], nums[::2] = s[:(len(s))//2], s[(len(s))//2:]
Runtime: 172 ms, faster than 88.36% of Python3 online submissions for Wiggle Sort II.
Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.
相当于。。
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
arr = sorted(nums)
for i in range(1, len(nums), 2):
nums[i] = arr.pop()
for i in range(0, len(nums), 2):
nums[i] = arr.pop()
Runtime: 184 ms, faster than 50.38% of Python3 online submissions for Wiggle Sort II.
Memory Usage: 15.5 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.
用骚操作反而时间复杂度更低😂😂
光头大佬的魔法代码
https://leetcode.com/problems/wiggle-sort-ii/discuss/77678/3-lines-Python-with-Explanation-Proof
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
nums.sort()
half = len(nums[::2])
nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]
Runtime: 172 ms, faster than 88.12% of Python3 online submissions for Wiggle Sort II.
Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
nums.sort()
half = len(nums[::2])-1
nums[::2], nums[1::2] = nums[half::-1], nums[:half:-1]
Runtime: 172 ms, faster than 88.17% of Python3 online submissions for Wiggle Sort II.
Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
for i, num in enumerate(sorted(nums, reverse=True)):
nums[(1+2*i) % (len(nums) | 1)] = num
Runtime: 176 ms, faster than 74.05% of Python3 online submissions for Wiggle Sort II.
Memory Usage: 15.5 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.
虚拟指针
https://leetcode.com/problems/wiggle-sort-ii/discuss/77677/O(n)%2BO(1)-after-median-Virtual-Indexing
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
import random
n = len(nums)
k = len(nums)//2
if len(set(nums)) > 100:
random.shuffle(nums)
def partition(nums, left, right):
i = left-1
povit = nums[right]
for j in range(left, right):
if nums[j] < povit:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1], nums[right] = nums[right], nums[i+1]
return i+1
left, right = 0, len(nums)-1
while left <= right:
pi = partition(nums, left, right)
if pi > k:
right = pi-1
elif pi < k:
left = pi + 1
else:
break
i, j = 0, k-1
while i <= j:
if nums[i] == nums[k]:
nums[i], nums[j] = nums[j], nums[i]
j -= 1
else:
i += 1
i, j = k+1, n-1
while i <= j:
if nums[j] == nums[k]:
nums[i], nums[j] = nums[j], nums[i]
i += 1
else:
j -= 1
else:
nums.sort()
if n & 1 == 0:
nums[::2], nums[1::2] = nums[:k][::-1], nums[k:][::-1]
else:
nums[::2], nums[1::2] = nums[:k+1][::-1], nums[k+1:][::-1]
Runtime: 176 ms, faster than 74.05% of Python3 online submissions for Wiggle Sort II.
Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.
Last updated
Was this helpful?