LeetCode 题解工作台
摆动排序 II
给你一个整数数组 nums ，将它重新排列成 nums[0] nums[2] 的顺序。 你可以假设所有输入数组都可以得到满足题目要求的结果。 示例 1： 输入： nums = [1,5,1,1,6,4] 输出： [1,6,1,5,1,4] 解释： [1,4,1,5,1,6] 同样是符合题目要求的结果…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
class Solution: def wiggleSort(self, nums: List[int]) -> None:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
示例 1：
输入：nums = [1,5,1,1,6,4] 输出：[1,6,1,5,1,4] 解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
示例 2：
输入：nums = [1,3,2,2,3,1] 输出：[2,3,1,3,1,2]
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 5000- 题目数据保证，对于给定的输入
nums，总能产生满足题目要求的结果
进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
解题思路
方法一：排序
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
arr = sorted(nums)
n = len(arr)
i, j = (n - 1) >> 1, n - 1
for k in range(n):
if k % 2 == 0:
nums[k] = arr[i]
i -= 1
else:
nums[k] = arr[j]
j -= 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assess how the candidate applies the greedy approach to solve the problem efficiently.
- question_mark
Evaluate the candidate's ability to manage array manipulations and element positioning for this pattern.
- question_mark
Check for understanding of the 'wiggle' condition and whether the candidate can optimize the process using sorting or selective placement.
常见陷阱
外企场景- error
Overcomplicating the solution by trying to compare every adjacent pair rather than focusing on the greedy choice and invariant validation.
- error
Failing to correctly handle the array sorting step, which is essential for ensuring the correct wiggle order.
- error
Not performing a final check after rearranging the array to ensure that the wiggle condition holds for all elements.
进阶变体
外企场景- arrow_right_alt
Apply the same approach to larger datasets or arrays with different constraints for performance evaluation.
- arrow_right_alt
Implement a solution with an alternative sorting method or use partition-based techniques like Quickselect.
- arrow_right_alt
Test the approach by adding additional constraints, such as ensuring specific values in the array are placed at certain indices.