給定未排序的陣列
nums，原地重排使得nums[0] <= nums[1] >= nums[2] <= nums[3] ...（交替的小於等於和大於等於）。
Example:
Input: nums = [3,5,2,1,6,4] Output: [3,5,1,6,2,4]（任何滿足 wiggle 條件的排列皆可）
Intuition
TIP
核心思路：一次遍歷，若 index 為奇數時 nums[i] < nums[i-1]，或 index 為偶數時 nums[i] > nums[i-1]，就交換相鄰兩元素。
- 奇數位應該是局部最大（
nums[i] >= nums[i-1]） - 偶數位應該是局部最小（
nums[i] <= nums[i-1]） - 若不滿足就交換，交換不會破壞前面的 wiggle 性質
Approaches
1. Sort Then Swap — O(n log n) / O(1)
- Idea: 先排序，然後每兩個元素一組交換（swap
nums[1]和nums[2]，swapnums[3]和nums[4]…） - Time:
O(n log n)- 排序主導 - Space:
O(1)- 原地排序後原地交換
class Solution {
fun wiggleSort(nums: IntArray) {
nums.sort()
for (i in 1 until nums.size - 1 step 2) {
val temp = nums[i]
nums[i] = nums[i + 1]
nums[i + 1] = temp
}
}
}⭐ 2. One-Pass Greedy Swap — O(n) / O(1)
- Idea: 遍歷陣列，根據當前 index 的奇偶性判斷是否需要交換相鄰元素
- Time:
O(n)- 一次遍歷 - Space:
O(1)- 原地操作
class Solution {
fun wiggleSort(nums: IntArray) {
for (i in 1 until nums.size) {
if ((i % 2 == 1 && nums[i] < nums[i - 1]) ||
(i % 2 == 0 && nums[i] > nums[i - 1])) {
val temp = nums[i]
nums[i] = nums[i - 1]
nums[i - 1] = temp
}
}
}
}WARNING
為什麼交換不會破壞前面已建立的 wiggle 性質？以奇數位為例：若 nums[i] < nums[i-1]，交換後 nums[i-1] 變更小，而偶數位 i-1 本就要求較小值，所以 i-2 到 i-1 的關係不會被破壞。
🔑 Takeaways
- Pattern: Wiggle / 交替排序 -> 局部性質的 Greedy 交換
- Key trick: 只看相鄰兩元素的局部關係，O(n) 一次遍歷解決問題。注意 Wiggle Sort II（324 題）要求嚴格不等式，解法不同且更難