給定不同整數的陣列
nums，重新排列使得每個元素都不等於其左右鄰居的平均值。
Example:
Input: nums = [1,2,3,4,5] Output: [1,2,4,5,3]（任何合法排列皆可）
Intuition
TIP
核心思路：排序後，交替放置較小和較大的元素（Wiggle Sort），保證每個元素不是鄰居的平均值。
- 如果排成鋸齒狀（小、大、小、大…），每個「大」都大於兩邊，每個「小」都小於兩邊
- 不等於平均值 = 不在兩個鄰居之間 = 比兩邊都大或都小
- 排序後用 Two Pointers 從兩端交替取值
Approaches
1. Sort + Re-interleave — O(n log n) / O(n)
- Idea: 排序後，分成前半（小值）和後半（大值），交替插入新陣列
- Time:
O(n log n)- 排序主導 - Space:
O(n)- 結果陣列
class Solution {
fun rearrangeArray(nums: IntArray): IntArray {
nums.sort()
val result = IntArray(nums.size)
var left = 0
var right = nums.size - 1
var idx = 0
while (idx < nums.size) {
result[idx] = nums[left++]
idx++
if (idx < nums.size) {
result[idx] = nums[right--]
idx++
}
}
return result
}
}⭐ 2. Sort + Swap into Wiggle — O(n log n) / O(1)
- Idea: 排序後，從 index 1 開始每隔一個做相鄰交換，保證偶數位 < 奇數位 > 偶數位
- Time:
O(n log n)- 排序主導 - Space:
O(1)- 原地操作（不計排序空間）
class Solution {
fun rearrangeArray(nums: IntArray): IntArray {
nums.sort()
// 每次取兩個相鄰元素交換，使得排列呈鋸齒狀
var i = 1
while (i < nums.size - 1) {
val temp = nums[i]
nums[i] = nums[i + 1]
nums[i + 1] = temp
i += 2
}
return nums
}
}WARNING
所有元素互不相同是此題的重要前提，否則 Wiggle Sort 不一定能保證嚴格不等。
🔑 Takeaways
- Pattern: Wiggle Sort / 鋸齒排列
- Key trick: 排序後相鄰交換產生鋸齒效果；「不等於鄰居平均」等價於「嚴格大於或嚴格小於兩鄰居」