給定一個 m x n 的二維網格和一個整數
k，將網格中的每個元素向右移動k次。每次移動時，最後一行最後一列的元素移到第一行第一列。
Example:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[9,1,2],[3,4,5],[6,7,8]]
Intuition
TIP
核心思路：將二維座標轉為一維索引，位移後再轉回二維座標。
- 二維網格的移位等同於將其攤平成一維陣列後做循環右移
- 一維索引
idx對應二維座標(idx / n, idx % n) - 位移後的新索引
(idx + k) % (m * n)
Approaches
1. Simulate Shifting — O(k * m * n) / O(m * n)
- Idea: 直接模擬 k 次移位操作
- Time:
O(k * m * n)- k 次移位，每次遍歷整個矩陣 - Space:
O(m * n)- 暫存矩陣
class Solution {
fun shiftGrid(grid: Array<IntArray>, k: Int): List<List<Int>> {
val m = grid.size
val n = grid[0].size
val total = m * n
val effectiveK = k % total
var current = grid.map { it.toList() }.toMutableList()
repeat(effectiveK) {
val newGrid = Array(m) { IntArray(n) }
for (i in 0 until m) {
for (j in 0 until n) {
val newIdx = (i * n + j + 1) % total
newGrid[newIdx / n][newIdx % n] = current[i][j]
}
}
current = newGrid.map { it.toList() }.toMutableList()
}
return current
}
}⭐ 2. 1D Index Mapping — O(m * n) / O(m * n)
- Idea: 將二維攤平為一維，計算每個元素位移後的新位置，直接放入結果
- Time:
O(m * n)- 遍歷一次 - Space:
O(m * n)- 結果矩陣
class Solution {
fun shiftGrid(grid: Array<IntArray>, k: Int): List<List<Int>> {
val m = grid.size
val n = grid[0].size
val total = m * n
val result = Array(m) { IntArray(n) }
for (i in 0 until m) {
for (j in 0 until n) {
val newIdx = (i * n + j + k) % total
result[newIdx / n][newIdx % n] = grid[i][j]
}
}
return result.map { it.toList() }
}
}🔑 Takeaways
- Pattern: 二維與一維索引互轉——
idx = row * cols + col、row = idx / cols、col = idx % cols - Key trick: 循環位移用取餘數
(idx + k) % total處理；先算k % total可避免多餘的操作