1260. Shift 2D Grid

Easy
Description

給定一個 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#

核心思路：將二維座標轉為一維索引，位移後再轉回二維座標。

  • 二維網格的移位等同於將其攤平成一維陣列後做循環右移
  • 一維索引 idx 對應二維座標 (idx / n, idx % n)
  • 位移後的新索引 (idx + k) % (m * n)

Approaches#

1: 模擬移位#

  • 概念: 直接模擬 k 次移位操作
  • 時間複雜度: O(k * m * n) - k 次移位，每次遍歷整個矩陣
  • 空間複雜度: 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: 一維索引映射#

  • 概念: 將二維攤平為一維，計算每個元素位移後的新位置，直接放入結果
  • 時間複雜度: O(m * n) - 遍歷一次
  • 空間複雜度: 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
  • 關鍵技巧: 循環位移用取餘數 (idx + k) % total 處理；先算 k % total 可避免多餘的操作