Description
給定陣列
nums，由 2n 個元素組成，格式為[x1,x2,...,xn,y1,y2,...,yn]。回傳以[x1,y1,x2,y2,...,xn,yn]格式排列的陣列。
Example:
Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7]
Intuition#
核心思路：前半部取
nums[i]、後半部取nums[i+n]，交替放入結果陣列。
- 前 n 個元素是 x 組，後 n 個是 y 組
- 結果是 x 和 y 交替排列：x1, y1, x2, y2, …
- 進階：可以用位元操作在 O(1) 空間內完成（利用數值範圍 <= 1000，用高位存第二個值）
Approaches#
1: 額外陣列#
- 概念: 建立新陣列，交替從前半和後半取值
- 時間複雜度:
O(n) - 空間複雜度:
O(n)- 結果陣列
class Solution {
fun shuffle(nums: IntArray, n: Int): IntArray {
val result = IntArray(2 * n)
for (i in 0 until n) {
result[2 * i] = nums[i]
result[2 * i + 1] = nums[i + n]
}
return result
}
}⭐2: 位元打包（O(1) 額外空間）#
- 概念: 因為值 <= 1000（< 2^10），可以把兩個值打包在一個 int 裡：高位存新值，低位存原值。最後再解包
- 時間複雜度:
O(n) - 空間複雜度:
O(1)- 原地操作（不算輸出）
class Solution {
fun shuffle(nums: IntArray, n: Int): IntArray {
// 將配對資訊存入高位（值 <= 1000 < 1024 = 2^10）
for (i in 0 until n) {
nums[i] = nums[i] or (nums[i + n] shl 10)
}
// 從後往前解包，避免覆蓋未處理的資料
for (i in n - 1 downTo 0) {
val x = nums[i] and 0x3FF // 低 10 位
val y = (nums[i] shr 10) and 0x3FF // 高 10 位
nums[2 * i] = x
nums[2 * i + 1] = y
}
return nums
}
}🔑 Takeaways#
- Pattern: 位元打包——利用數值範圍限制，將多個值存在一個整數中
- 關鍵技巧: 當值的範圍已知且不大時，可以用高位/低位分別存兩個值，實現 O(1) 空間的原地操作