有一个nxn整数矩阵,请编写一个算法,将矩阵原地顺时针旋转90度。
给定一个nxn的矩阵,和矩阵的阶数n,请原地旋转矩阵。
数据范围:,矩阵中的值满足
要求:空间复杂度 ,时间复杂度
解题思路:先转置,后进行每一行翻转
import java.util.*; public class Solution { public void rotateMatrix (ArrayList<ArrayList<Integer>> mat, int n) { for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { int temp = mat.get(i).get(j); mat.get(i).set(j, mat.get(j).get(i)); mat.get(j).set(i, temp); } } for(int i = 0; i < n; ++i) { for(int j = 0; j < n / 2; ++j) { int temp = mat.get(i).get(j); mat.get(i).set(j, mat.get(i).get(n - j - 1)); mat.get(i).set(n - j - 1, temp); } } } }
package main //import "fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param mat int整型二维数组 * @param n int整型 * @return void */ func rotateMatrix( mat [][]int , n int ) { arr:=[]int{} for i:=0;i<n;i++{ for j:=n-1;j>=0;j--{ arr=append(arr,mat[j][i]) } } idx:=0 for i:=0;i<n;i++{ for j:=0;j<n;j++{ mat[i][j]=arr[idx] idx++ } } }
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param mat int整型二维数组 # @param n int整型 # @return void # class Solution: """ 题目: https://www.nowcoder.com/practice/5b7029aae0f84935b3ac9fad9e33a246?tpId=196&tqId=40549&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 算法: 顺时针旋转90° ==> 1. 按主对角线翻转 2. 按行翻转 复杂度: 时间复杂度:O(mn) 空间复杂度:O(1) """ def rotateMatrix(self, mat, n): # write code here for i in range(1, n): for j in range(i): mat[i][j], mat[j][i] = mat[j][i], mat[i][j] for i in range(n): mat[i].reverse() return mat if __name__ == "__main__": sol = Solution() matrix, n = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], 3 res = sol.rotateMatrix(matrix, n) print res
import java.util.*; public class Solution { public void rotateMatrix (ArrayList<ArrayList<Integer>> mat, int n) { if(mat == null || n == 0) return; //将上三角和下三角进行交换 for(int i = 1;i < n;i ++) { for(int j = 0;j < i;j ++) { int temp = mat.get(i).get(j); mat.get(i).set(j,mat.get(j).get(i)); mat.get(j).set(i,temp); } } //将每一行进行反转 for(ArrayList<Integer> list : mat) { Collections.reverse(list); } } }