解題說明
Wiggle Sort
題目描述:
給定一個未排序的整數陣列 nums,原地重新排列使得 nums[0] <= nums[1] >= nums[2] <= nums[3] >= ...,即奇數索引的元素不小於相鄰元素,偶數索引的元素不大於相鄰元素。
解題思路: 觀察規律:
- 偶數索引
i:nums[i] <= nums[i+1] - 奇數索引
i:nums[i] >= nums[i+1]
只需一次遍歷:對於每個位置 i,檢查是否違反上述條件。若違反,將 nums[i] 和 nums[i-1] 交換即可。
為什麼交換是安全的?
- 若
i為奇數且nums[i] < nums[i-1]:交換後nums[i-1]變小,不會破壞i-1(偶數位)的<=條件。 - 若
i為偶數且nums[i] > nums[i-1]:交換後nums[i-1]變大,不會破壞i-1(奇數位)的>=條件。
C++ 解法
複雜度分析
時間複雜度:O(n) — 單次遍歷陣列,每個元素最多檢查和交換一次。
空間複雜度:O(1) — 原地操作,只用常數額外空間。
虛擬碼
1. For each index i from 1 to n-1: a. If i is odd and nums[i] < nums[i-1]: swap nums[i] and nums[i-1] b. If i is even and nums[i] > nums[i-1]: swap nums[i] and nums[i-1]
其他解法
排序 + 交換 O(n log n):先排序陣列,再從索引 2 開始每隔一個交換相鄰元素(swap(nums[i], nums[i-1]) for i = 2, 4, 6, ...)。排序保證小值在前,交換產生鋸齒形。正確但時間複雜度不如貪心法。
三路分區 + 交叉放置 O(n):類似 Wiggle Sort II(LeetCode 324)的做法,先找中位數再三路分區。對本題而言過度設計,因為本題允許相等(<= 和 >=),不需要嚴格交替。
延伸思考
- 如果條件改為嚴格不等式
nums[0] < nums[1] > nums[2] < nums[3] > ...(LeetCode 324 Wiggle Sort II),為什麼簡單交換法不再適用? - 貪心交換法的正確性證明:為什麼修復當前位置不會破壞已修復的前一個位置?
- 如果要求字典序最小的 wiggle 排列,該如何修改算法?