http://www.cnblogs.com/yrbbest/p/5165084.html
记得有道Amazon的OA题目,好像是给定一个矩阵,让把矩阵的每个元素向右shift一个位置。这道题之前没有好好自习想过。今天正好刷到了rotate matrix,所以正好一块想了。
思路是类似LeetCode Spiral Matrix:
- 假设矩阵为方阵
- 设置top, left, bot, right四个边界变量,然后从最外圈到最内圈一圈一圈的shift。
- 设定一个count,当count < total elements in matrix的时候进行shift
- 在每一圈开始的时候记录下来matrix[top][left],然后开始shift
- 从top到bot
- 从left到right
- 从bot到top
- 从right到left
- 在最后一条边的结果尝试更新新的matrix[top][left],这时候的top为旧的,而left已经更新过一次了, 我们要分为两种情况考虑
- count != totalElements - 1, 这时候我们要:
- matrix[top][left] 更新为tmp
- count++
- top++
- 进入下一圈
- 否则 count == totalElements - 1,也要分为两种情况
- totalElements为奇数,我们不改变matrix[top][left]
- totalElements为偶数,这时我们依然要更新一次matrix[top][left] = tmp
- 然后count++结束循环返回结果
- count != totalElements - 1, 这时候我们要:
- 在最后一条边的结果尝试更新新的matrix[top][left],这时候的top为旧的,而left已经更新过一次了, 我们要分为两种情况考虑
- 假如给定矩阵不为方阵,则我们还要加入更多判断,比如剩下最后一行或者最后一列的时候不更新之类的。最后一行或者最后一列可以由bot - top 或者 right - left分别求出
Time Complexity - O(mn),Space Complexity - O(1), in place。
public void rotateMatrixByOne(int[][] matrix) { if (matrix == null || matrix[0] == null) { return; } int m = matrix.length; int n = matrix[0].length; int left = 0, top = 0, right = n - 1, bot = m - 1; int count = 0; int totalElements = m * n; while (count < totalElements) { int tmp = matrix[top][left]; if (count < totalElements) { for (int i = top; i < bot; i++) { matrix[i][left] = matrix[i + 1][left]; count++; } left++; } if (count < totalElements) { for (int i = left - 1; i < right; i++) { matrix[bot][i] = matrix[bot][i + 1]; count++; } bot--; } if (count < totalElements) { for (int i = bot + 1; i > top; i--) { matrix[i][right] = matrix[i - 1][right]; count++; } right--; } if (count < totalElements) { for (int i = right + 1; i > left; i--) { matrix[top][i] = matrix[top][i - 1]; count++; } if (count != totalElements - 1) { matrix[top][left] = tmp; } else if (totalElements % 2 == 0) { matrix[top][left] = tmp; } count++; top++; } } }