Algorithms to Shift a 2D Grid/Matrix In-Place

  • 时间:2020-09-17 10:57:36
  • 分类:网络文摘
  • 阅读:100 次

Given a 2D grid of size n * m and an integer k. You need to shift the grid k times.

In one shift operation:

  • Element at grid[i][j] becomes at grid[i][j + 1].
  • Element at grid[i][m – 1] becomes at grid[i + 1][0].
  • Element at grid[n – 1][m – 1] becomes at grid[0][0].
  • Return the 2D grid after applying shift operation k times.

Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
matrix1 Algorithms to Shift a 2D Grid/Matrix In-Place algorithms c / c++ math

Example 2:
Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
matrix2 Algorithms to Shift a 2D Grid/Matrix In-Place algorithms c / c++ math

Example 3:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:
1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Hints:
Simulate step by step. move grid[i][j] to grid[i][j+1]. handle last column of the grid.
Put the matrix row by row to a vector. take k % vector.length and move last k of the vector to the beginning. put the vector to the matrix back the same way.

How to Shift a 2D Grid/Matrix in 2D?

The last element in the 2D Grid/Matrix needs to be overwritten first, thus value needs to be saved. Then, we can start shifting backwards from the last row, last column. Special cases have to be taken care when dealing with the first element (as it should be set the original last value), and the first columns need to be taking its previous row and last column.

Therefore, many conditions are existen in the loop, which could be unrolled.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        for (int i = 0; i < k; ++ i) {
            int n = grid.size();
            int m = grid[0].size();
            int last = grid[n - 1][m - 1];
            for (int row = n - 1; row >= 0; -- row) {
                for (int col = m - 1; col >= 0; -- col) {
                    if ((row == 0) && (col == 0)) { // first element
                        grid[0][0] = last;
                    } else {
                        if (col == 0) { // first column
                            grid[row][col] = grid[row - 1][m - 1];
                        } else {
                            grid[row][col] = grid[row][col - 1];
                        }
                    }                    
                }
            }
        }
        return grid;
    }
};
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        for (int i = 0; i < k; ++ i) {
            int n = grid.size();
            int m = grid[0].size();
            int last = grid[n - 1][m - 1];
            for (int row = n - 1; row >= 0; -- row) {
                for (int col = m - 1; col >= 0; -- col) {
                    if ((row == 0) && (col == 0)) { // first element
                        grid[0][0] = last;
                    } else {
                        if (col == 0) { // first column
                            grid[row][col] = grid[row - 1][m - 1];
                        } else {
                            grid[row][col] = grid[row][col - 1];
                        }
                    }                    
                }
            }
        }
        return grid;
    }
};

You could unroll the IF conditions and take care of the first columns, and first row especially.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        for (int i = 0; i < k; ++ i) {
            int n = grid.size();
            int m = grid[0].size();
            int last = grid[n - 1][m - 1];
            for (int row = n - 1; row > 0; -- row) {
                for (int col = m - 1; col > 0; -- col) {
                    grid[row][col] = grid[row][col - 1];
                }
                grid[row][0] = grid[row - 1][m - 1]; // first column
            }
            for (int col = m - 1; col > 0; -- col) { // first row
                grid[0][col] = grid[0][col - 1];
            }
            grid[0][0] = last; // first element
        }
        return grid;
    }
};
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        for (int i = 0; i < k; ++ i) {
            int n = grid.size();
            int m = grid[0].size();
            int last = grid[n - 1][m - 1];
            for (int row = n - 1; row > 0; -- row) {
                for (int col = m - 1; col > 0; -- col) {
                    grid[row][col] = grid[row][col - 1];
                }
                grid[row][0] = grid[row - 1][m - 1]; // first column
            }
            for (int col = m - 1; col > 0; -- col) { // first row
                grid[0][col] = grid[0][col - 1];
            }
            grid[0][0] = last; // first element
        }
        return grid;
    }
};

How to Shift a 2D Grid/Matrix in 1D?

We know the total elements are row*column thus, we can loop backwards a single index, then converting to row and column indices. This helps to make a single loop concise. The first element needs to be handled (special case).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        for (int i = 0; i < k; ++ i) {
            int n = grid.size();
            int m = grid[0].size();
            int last = grid[n - 1][m - 1];
            for (int i = m * n - 1; i > 0; -- i) {
                int row = i / m;
                int col = i % m;
                int row1 = (i - 1) / m;
                int col1 = (i - 1) % m;
                grid[row][col] = grid[row1][col1];
            }
            grid[0][0] = last;
        }
        return grid;
    }
};
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        for (int i = 0; i < k; ++ i) {
            int n = grid.size();
            int m = grid[0].size();
            int last = grid[n - 1][m - 1];
            for (int i = m * n - 1; i > 0; -- i) {
                int row = i / m;
                int col = i % m;
                int row1 = (i - 1) / m;
                int col1 = (i - 1) % m;
                grid[row][col] = grid[row1][col1];
            }
            grid[0][0] = last;
        }
        return grid;
    }
};

All above C++ implementations are O(RC) time where R is the row number and C is the number of the columns for the 2D Grid. Alternatively, we can say it is O(N) where N is the number of elements in the 2D Grid/Matrix. The space requirement is O(1) constant as we are shifting the 2D array/matrix in place without allocating extra arrays.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
素食的分类及适当素食具有的保健作用  冬季咳嗽吃什么自制美味止咳小零食  冬季进补鸡汤要注意 几类人不宜喝鸡汤  芦荟的保健价值、食用禁忌及食用方法  冬季食疗养生:吃南瓜可有效治疗哮喘  食疗:有效增强男人性能力的八款药膳  枸杞保健食疗功效多补肾益精养肝明目  如何从感官上辨别枸杞的真假和质量优劣  红酒对人体有保健作用但并非人人适宜  食品安全:盘点有毒的11种常见食物 
评论列表
添加评论