网站备案 和 icp,惠州热门的网站,o2o电子商务模式,wordpress 页面权限原题链接
旋转图像备战技术面试#xff1f;力扣提供海量技术面试资源#xff0c;帮助你高效提升编程技能#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/rotate-image/
算法分析 若矩阵的行列数为N#xff0c;设i表示行索引#xff0c;i属…原题链接
旋转图像备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/rotate-image/
算法分析 若矩阵的行列数为N设i表示行索引i属于[1,N]按照题意旋转矩阵则可以理解为我们需要将第i行的所有元素转换为第N-i1列如示例1所示第1行为[1,2,3]旋转后的第1行则变成了第3列第2行与第3行同样如此。 图1 图2 PS:经现有测试该方法适用于行列数相同的矩阵但不确定是否适用于行列数不同的矩阵。 如图1索引分别为(0,0)(0,1)(0,2)(0,3)(1,3)(2,3)(3,3)(3,2)(3,1)(3,0)(2,0)(1,0)的点围成了一个圈假设我们称之为矩阵圈。那么由外向内我们依次称为第1层矩阵圈第2层矩阵圈……第n层矩阵圈。图1所示有两个矩阵圈第1层矩阵圈的索引集合为[(0,0)(0,1)(0,2)(0,3)(1,3)(2,3)(3,3)(3,2)(3,1)(3,0)(2,0)(1,0)]第2层矩阵圈的索引集合为[(1,1)(1,2)(2,2)(2,1)]。 如图1和图2我们可以发现通过对每个矩阵圈的旋转即可完成对整个矩阵的旋转而对矩阵圈的旋转实际上就是对矩阵圈进行点交换。点交换的意思是交换矩阵圈四个边上的点并且每个点是相互对应的。 如图3所示第一次交换索引为(0,0)和索引为(0,3)的点第二次交换索引为(0,0)和索引为(3,3)的点第三次交换索引为(0,0)和索引为(3,0)的点我们把这称为矩阵圈的点交换。而这仅仅是矩阵圈的第一次点交换假设该矩阵圈的行数和列数均为m那么旋转该矩阵圈则需要(m-1)次点交换。 图3 图4 图5 图6 图3456则为该矩阵圈的一次完整的90°旋转。 为了从定量角度分析这个规律。首先我们可以定义四个变量rowA,rowB,colA,colB分别表示每一个矩阵圈的首行尾行以及首列尾列并对它们进行初始化rowA0,rowBm-1,colA0,colBm-1rowA指向当前矩阵圈第一行rowB指向最后一行colA指向当前矩阵圈第一列colB指向最后一列。其次我们再定义一个变量count表示当前矩阵圈需要进行点交换的次数count属于[1,m-1]。那么该矩阵圈进行点交换的四个点的索引分别为
(rowA,colAcount-1), (rowAcount-1,colB),
(rowB,colB-count1), (rowB-count1,colA) 我们只需要按照(rowAcount-1,colB),(rowB,colB-count1),(rowB-count1,colA)的索引顺序分别与索引为(rowA,colAcount-1)的点进行交换即可每完成一次点交换则count进行1操作当count等于m-1时表示该矩阵圈的90°旋转完成。所以接下来需要收缩rowA,rowB,colA,colB四个变量从而指向下一层矩阵圈收缩操作即对rowA和colA进行1操作对rowB和colB进行-1操作重复上述过程从外向内旋转矩阵圈直至rowA、rowB、colA、colB四个变量的值相等则表明整个矩阵完成了90°的旋转。
代码示例C#
public void Rotate(int[][] matrix)
{//定义变量int rowA 0, rowB matrix.Length - 1, colA 0, colB matrix[0].Length - 1, count 1;//逻辑主体while (count colB - colA){//矩阵点交换(matrix[rowA][colA count - 1], matrix[rowA count - 1][colB]) (matrix[rowA count - 1][colB], matrix[rowA][colA count - 1]);(matrix[rowA][colA count - 1], matrix[rowB][colB - count 1]) (matrix[rowB][colB - count 1], matrix[rowA][colA count - 1]);(matrix[rowA][colA count - 1], matrix[rowB - count 1][colA]) (matrix[rowB - count 1][colA], matrix[rowA][colA count - 1]);//矩阵圈收缩if (count colB - colA){colA;colB--;rowA;rowB--;count 1;}else count;}
}
算法解说 结合算法分析过程我们将矩阵的旋转转换为矩阵圈的旋转然后将矩阵圈的旋转转换为矩阵点的交换也就是说矩阵旋转的本质就是矩阵中各个元素的交换实际上我们从图1和图2就可以发现转换前的矩阵的第一行变成了转换后的矩阵的最后一列但是本文的解题思路并未采取这种方式。 由于每个矩阵圈都有四条边所以旋转矩阵圈就是在交换四个边上指定的元素具体的思路算法分析中已经描述得比较详尽对于如何将分析过程转换为代码对于多数算法题来说本质上都是明确两个重点一个是变量一个是逻辑主体。本题中所用到的变量包括用于明确当前矩阵圈的四个指针还有一个用于记录当前矩阵圈进行点交换的次数。而逻辑主体则包括矩阵点交换和矩阵圈收缩同时需要明确逻辑主体退出的条件。
