c++旋转 题目难度：语法入门 时间限制：1000ms 内存限制：256MB 题目描述 给出一个 n×n 的 01 矩阵。 请你将其最外层的部分每个数沿顺时针 90° 移动一个格子后的结果输出。 输入格式 第一行包含 1 个正整数 n。 之后 n 行，给出 01 矩阵的形态。 输出格式 输出一个 n×n 的矩阵，表示答案。 样例数据 【样例 1 输入】 4 0101 1101 1111 0000 ​ 【样例 1 输出】 1010 1101 0111 0001 ​ 样例解释1 最外层的部分数字按顺时针方向依次为010111000011 所有数字顺延一格后，依次为101011100001，内部所有数字不发生改变。 【样例 2 输入】 5 01010 01001 10110 00110 01010 ​ 【样例 2 输出】 00101 11000 00111 00110 10100 ​ 数据说明 对于 60% 的数据，n≤2。 对于所有测评数据，2≤n≤10 3 。

<think>我们有一个n x n的01矩阵，要求只旋转最外层元素顺时针90度，而内层元素保持不变。 注意：题目要求只旋转最外层，所以我们需要识别矩阵的“层”。对于一个n x n矩阵，最外层就是第一圈（即边界上的元素）。 思路： 1. 我们不需要旋转整个矩阵，而是只处理最外层。 2. 最外层可以看作一个正方形的环，我们可以将这个环上的元素分成四部分：上边、右边、下边、左边。 3. 旋转90度，实际上就是将这四部分依次移动：上边移动到右边，右边移动到下边，下边移动到左边，左边移动到上边。 4. 但是，如果我们直接覆盖，那么我们需要一个临时数组来保存一层？或者我们可以通过一个临时变量来循环替换四个位置（类似于引用[2][3][4]中的原地旋转方法）？但是注意，题目要求只旋转最外层，而且内层不动，所以我们可以只处理最外层。 然而，题目要求是“旋转最外层元素”，注意旋转后，最外层元素的位置发生了变化。如果我们采用原地旋转，那么需要同时保存四个位置的值，然后进行交换。但是，如果我们只旋转最外层，那么我们可以使用一个临时数组来保存最外层的一圈，然后重新赋值。 有两种方法： 方法一：使用临时数组（可能更直观） 步骤： a. 提取最外层元素（按顺时针顺序：从上边（左到右）->右边（上到下）->下边（右到左）->左边（下到上）），形成一个一维数组。 b. 将这个一维数组进行旋转（比如，循环右移一行的长度？实际上，旋转90度相当于将整个环顺时针移动，原来上边的第一个元素会变成右边的第一个元素，而原来上边的最后一个元素会变成右边的最后一个元素？实际上，我们提取的顺序是上边、右边、下边、左边，那么旋转90度后，应该变成：左边（逆序，因为原来左边是从下到上，旋转后左边变成上边，需要逆序变成上边的顺序？）->上边->右边->下边（逆序）？这样比较麻烦。 方法二：原地交换（参考引用[2][4]的代码，但注意他们旋转的是整个矩阵，而且是一层一层向内，我们只需要处理最外层） 引用[2][4]中的方法都是原地旋转整个矩阵的每一层，我们只需要做最外层。我们可以用类似的方法，只处理最外层。 具体原地旋转方法（以最外层为例）： 假设矩阵大小为n x n，最外层有4*(n-1)个元素（除去四个角重复计算，实际上每边n-1个非公共元素，加上四个角，总数为4*(n-1)个元素？不对，实际上每边有n个元素，但四个角被两边共享，所以总元素数为4*(n-1)）。但是，我们旋转时，可以每次处理四个位置（一组四个元素，分别位于上、右、下、左四条边上），然后依次旋转。 旋转规律（以0-based索引）： 对于最外层，我们考虑行i=0（上边）到i=n-1（下边），列j=0（左边）到j=n-1（右边）。 我们只处理最外层，所以行索引i从0到n-1，但内层不处理。具体来说，我们只处理第一行和最后一行，以及第一列和最后一列，但注意四个角不要重复处理。 实际上，我们可以将最外层分成四个部分： - 上边：行=0，列从0到n-1 - 右边：行从0到n-1，列=n-1 - 下边：行=n-1，列从n-1到0 - 左边：行从n-1到0，列=0 但是，这样描述在旋转时，我们可以用四个位置为一组： 例如，对于上边的一个点(i, j)（其中i=0, j从0到n-2，注意最后一个元素属于右边，所以不重复取），实际上我们取四个位置： A: (i, j) // 上边 B: (j, n-1-i) // 右边：注意这里，实际上旋转后，上边的元素会到右边，但是位置对应关系需要调整。 实际上，更标准的做法是（参考引用[4]的代码）： temp = matrix[i][j]; matrix[i][j] = matrix[n-1-j][i]; // 这里实际上是将左下角的元素放到左上角？不对，我们再看。 引用[4]中的代码是旋转整个矩阵90度，而且是一层一层旋转。我们只需要最外层，所以我们可以用类似的方法，但是只做最外层（即i从0到n/2-1，但这里我们只做最外层，所以i=0，然后内层不做）。 但是，注意引用[4]的代码中，外层循环是i从0到n/2，内层循环j从i到n-1-i-1。这样，当i=0时，j从0到n-1-0-1，即j从0到n-2，这样处理的是最外层除了四个角以外的边上的点？不对，实际上四个角也会被处理，因为每个角都是四个位置交换的一部分。 所以，我们可以采用引用[4]的代码，但是只做最外层（即i=0）？但是注意，引用[4]的代码是旋转整个矩阵（所有层），我们只需要最外层，所以我们可以将外层循环限制在i=0（如果n>1，那么最外层需要旋转，但内层不做，所以内层循环就不做了）。但是，如果n=1，则不需要旋转。 然而，题目要求只旋转最外层，所以内层不动。因此，我们只需要进行最外层的旋转（即i=0这一层）。 引用[4]的代码（只做最外层）： for(int j=i; j<n-1-i; j++) // 这里i=0，所以j从0到n-2（因为n-1-0-1 = n-2） 然后交换四个位置： temp = matrix[i][j]; // (0,j) matrix[i][j] = matrix[n-1-j][i]; // 将(0,j)位置用(n-1-j,0)位置的值覆盖 matrix[n-1-j][i] = matrix[n-1-i][n-1-j]; // 将(n-1-j,0)位置用(n-1, n-1-j)位置的值覆盖 matrix[n-1-i][n-1-j] = matrix[j][n-1-i]; // 将(n-1, n-1-j)位置用(j, n-1)位置的值覆盖 matrix[j][n-1-i] = temp; // 将(j, n-1)位置用原来的(0,j)的值覆盖 注意：这个交换过程实际上是将四个位置（上边、左边、下边、右边）的元素逆时针旋转了90度？还是顺时针？我们验证一下： 假设我们有一个2x2矩阵： a b c d 按照上面的代码，i=0, j=0（因为n=2，j从0到0（n-1-i-1=2-0-1=1，所以j<1，即j=0）） temp = matrix[0][0] = a matrix[0][0] = matrix[2-1-0][0] = matrix[1][0] = c matrix[1][0] = matrix[2-1-0][2-1-0] = matrix[1][1] = d matrix[1][1] = matrix[0][2-1-0] = matrix[0][1] = b matrix[0][1] = temp = a 旋转后： c a d b 而顺时针旋转90度应该是： c a -> 顺时针旋转90度后应该是： 原来位置(0,0)的a旋转后应该在(0,1)的位置 原来位置(0,1)的b旋转后应该在(1,1)的位置 原来位置(1,0)的c旋转后应该在(0,0)的位置 原来位置(1,1)的d旋转后应该在(1,0)的位置 所以旋转后应该是： c a d b -> 不对，我们期望的是： 旋转90度后： c a -> 这不对，因为旋转90度后应该是： 第一行：c d 第二行：a b ？不对，重新想。 实际上，顺时针旋转90度后，矩阵应该是： c a -> 不对，应该是： 原矩阵： a b c d 顺时针旋转90度后： c a d b -> 这不对，正确的结果应该是： b d a c ？不对。 正确旋转90度： 旋转90度：行变列，列变行，并且行序逆序（或者列序逆序？） 具体：新矩阵的第一行是原矩阵的第一列的逆序：原第一列是[c, d]^T，逆序变成d, c？不对，应该是原矩阵的第一列（从上到下）变成新矩阵的第一行（从左到右）是c, d？不对。 正确的旋转90度： 新矩阵的(i,j)位置 = 原矩阵的(n-1-j, i)位置？ 验证：原矩阵位置(0,0) -> 新位置(0,0)应该等于原矩阵(n-1-0,0)=(n-1,0)？不对。 实际上，顺时针旋转90度：新矩阵的(i,j) = 原矩阵的(n-1-j, i) ？不对，应该是：新矩阵的(i,j) = 原矩阵的(j, n-1-i) 验证：原矩阵(0,0) -> 新矩阵(0,0)位置应该等于原矩阵(0, n-1-0) = (0,1) -> 这是b，但旋转后(0,0)应该是c（原矩阵(1,0)）? 不对。 另一种常用公式：顺时针旋转90度：matrix[i][j] -> matrix[j][n-1-i] 原矩阵(0,0) -> 新矩阵(0, n-1) -> 不对，我们希望原(0,0)变成新矩阵(0,0)位置？不对，旋转后位置会变。 我们重新思考：旋转后，原矩阵的第一行会变成新矩阵的最后一列。 原矩阵第一行： [a, b] 旋转90度后，应该变成新矩阵的最后一列： [a, b]^T 作为最后一列，即新矩阵第一行第二列是a，第二行第二列是b？不对，应该是： 新矩阵： 第一行：c, a -> 不对，应该是： 第一行：c, d 第二行：a, b -> 也不对。 正确顺时针旋转90度： 原矩阵： a b c d 顺时针旋转90度后： c a d b -> 这个结果不对，因为顺时针旋转90度后，a应该到b的位置，b应该到d的位置，d应该到c的位置，c应该到a的位置？不对。 实际上，顺时针旋转90度后： 原矩阵： (0,0)=a, (0,1)=b (1,0)=c, (1,1)=d 旋转后： (0,0)=c, (0,1)=a (1,0)=d, (1,1)=b -> 这个结果就是上面的交换结果。但是，我们期望的顺时针旋转90度应该是： a->(0,1), b->(1,1), c->(0,0), d->(1,0) 所以新矩阵应该是： (0,0)=c, (0,1)=a (1,0)=d, (1,1)=b -> 这个结果就是上面代码运行的结果。所以代码是顺时针旋转90度。 但是，我们通常认为顺时针旋转90度后，矩阵应该是： c d a b -> 不对，因为旋转后，原矩阵的第一行变成新矩阵的最后一列，而且顺序不变，所以应该是： 新矩阵第一行：c, a -> 不对，应该是： 新矩阵第一行：c, d 新矩阵第二行：a, b -> 这样才是我们通常认为的旋转（即行变成列，且第一行变成最后一列，且顺序不变？） 通常的旋转90度（顺时针）： 原矩阵： 1 2 3 4 5 6 7 8 9 顺时针旋转90度后： 7 4 1 8 5 2 9 6 3 按照引用[4]的代码（整个矩阵旋转）： 我们取最外层（3x3）： i=0, j从0到1（因为n=3，n-1-i-1=3-1-0-1=1，所以j=0,1） 当j=0: 交换四个位置： (0,0) -> (2,0) -> (2,2) -> (0,2) -> (0,0)的临时值 具体： temp = mat[0][0] = 1 mat[0][0] = mat[2][0] = 7 mat[2][0] = mat[2][2] = 9 mat[2][2] = mat[0][2] = 3 mat[0][2] = temp = 1 此时矩阵变成： 7 2 1 4 5 6 9 8 3 -> 注意，我们只换了四个角：1,7,9,3 -> 7,9,3,1 然后j=1: temp = mat[0][1] = 2 mat[0][1] = mat[2-1][0] = mat[1][0]=4 mat[1][0] = mat[2-0-1][2-1] = mat[1][2]=6 -> 注意，这里索引是：n-1-i=2, n-1-j=1 -> (2,1)位置？不对，代码中写的是：matrix[n-1-j][i] -> 这里i=0, n-1-j=2-1=1 -> (1,0)位置？不对，代码中第二个位置是：matrix[n-1-j][i] -> 这里i=0，所以是列0，行n-1-j=3-1-1=1? 所以位置是(1,0)=4 然后第三个位置：matrix[n-1-i][n-1-j] = matrix[2][1]=8 第四个位置：matrix[j][n-1-i]=matrix[1][2]=6 -> 这里代码中写的是：matrix[j][n-1-i] -> j=1, n-1-i=2 -> (1,2)=6 交换： mat[0][1] = 4 mat[1][0] = 6 -> 这里注意，我们刚刚把mat[1][0]覆盖为6，但是原来mat[1][0]是4，已经被覆盖了，然后： mat[2][1] = 6? 不对，代码中第三步：mat[2][1] = mat[1][2] -> 但是mat[1][2]已经被覆盖了吗？注意，我们第一步只换了四个角，第二步换的是中间边上的四个点。 这个交换过程比较复杂，容易出错。而且题目要求只旋转最外层，所以我们可以不用这种原地交换，而是用临时数组保存最外层，然后重新赋值。 方法一（使用临时数组）步骤： 1. 提取最外层元素（按顺时针顺序）：从(0,0)开始，到(0,n-1)，然后到(1,n-1),...直到(n-1,n-1)，然后到(n-1,n-2),...直到(n-1,0)，然后到(n-2,0),...直到(1,0)。注意，四个角不要重复。 2. 将这个环（一维数组）进行旋转：旋转90度相当于将这个环整体向右循环移动（n-1）个位置？因为环的长度为4*(n-1)，但旋转90度相当于每个元素移动（环的长度/4）的整数倍？不对，实际上，旋转90度相当于每个元素在环上移动（环的长度/4）步（即n-1步）。例如，环上第一个元素（上边第一个）旋转90度后，会变成右边第一个（即从位置0移动到位置(n-1)）。 3. 将旋转后的环重新赋值给最外层。 具体： 环的长度：L = 4*(n-1) （当n>1时，n=1时直接返回） 提取：我们按顺序提取： top: 行0，列0到n-1（共n个元素） right: 列n-1，行1到n-2（共n-2个元素） 注意：上下两个角已经被提取 bottom: 行n-1，列n-2到0（共n-1个元素？但是要倒序）-> 实际上，我们提取整个环，所以可以： 上边：从(0,0)到(0,n-1) 右边：从(1,n-1)到(n-2,n-1) [注意，跳过(0,n-1)和(n-1,n-1)已经在上边和下边提取了] 下边：从(n-1,n-1)到(n-1,0) [倒序：即从右到左] 左边：从(n-1,0)到(1,0) [倒序：从下到上] 但是这样提取，四个角会重复？所以我们需要避免重复。 通常提取环（顺时针）： top: (0,0) -> (0,1) -> ... -> (0, n-1) right: (1, n-1) -> (2, n-1) -> ... -> (n-2, n-1) bottom: (n-1, n-1) -> (n-1, n-2) -> ... -> (n-1, 0) [这里从右到左] left: (n-1,0) -> (n-2,0) -> ... -> (1,0) [从下到上] 这样，四个角都在top和bottom中出现了，而right和left没有包含四个角。所以整个环是：top（包含两个角）-> right（不含角）-> bottom（包含两个角，且顺序是逆的）-> left（不含角，且顺序是逆的）？这样提取后，环的顺序是： [ (0,0), (0,1), ..., (0,n-1), (1,n-1), (2,n-1), ..., (n-2,n-1), (n-1,n-1), (n-1,n-2), ..., (n-1,0), (n-2,0), ..., (1,0) ] 环的长度：n（上边）+ (n-2)（右边）+ n（下边）+ (n-2)（左边） = 4n-4 = 4*(n-1)，正确。 然后，我们如何旋转这个环90度？顺时针旋转90度，相当于环上的每个元素在环上的位置向后移动（n-1）个位置？因为环总长L=4*(n-1)，旋转90度相当于移动L/4 = n-1步。所以，我们可以将整个环向右循环移动n-1步。 例如，n=3，环长=8，移动2步（n-1=2）： 原始环： [a0, a1, a2, a3, a4, a5, a6, a7] -> 移动2步后： [a6, a7, a0, a1, a2, a3, a4, a5] 然后，我们将移动后的环重新按照原来的顺序放回最外层。 但是，重新赋值时，我们按照原来的顺序： 上边：从(0,0)到(0,2) -> 环的前3个元素（但实际环移动后，前三个元素是原环的最后两个和第一个？） 右边：从(1,2)到(1,2)（因为n=3，右边只有一个元素）-> 环的第4个元素（因为上边3个，所以右边从第3个开始？不对，环是连续的） 我们需要按照原来提取的顺序，将移动后的环拆分成四部分，然后依次填入。 步骤： 1. 创建一个长度为L=4*(n-1)的数组temp。 2. 按顺序提取最外层的元素到temp中（顺序如上所述）。 3. 创建一个新数组rotated，长度为L，将temp中的元素循环右移n-1位：即rotated[k] = temp[(k - (n-1) + L) % L] 或者左移？我们要求顺时针旋转90度，相当于环上每个元素移动到它原来位置顺时针方向n-1个位置后的位置。所以，新的位置i对应原来的位置(i - (n-1)) mod L，但是循环右移n-1位相当于将整个数组向右移动n-1位，即： rotated[i] = temp[(i - (n-1) + L) % L] -> 不对，循环右移k位：新位置i的元素来自原位置(i-k) mod L，但这里我们要求的是：原来在位置j的元素，移动后到了位置(j+(n-1)) mod L。所以我们也可以直接构建一个新数组：rotated[i] = temp[(i + (L - (n-1))) % L] 或者更简单：循环左移n-1位？不对，应该是循环右移n-1位。 循环右移n-1位：rotated[i] = temp[(i - (n-1) + L) % L] 或者用： rotated[(i + (n-1)) % L] = temp[i] -> 这样，新位置是原位置i加上n-1，然后模L。 但通常，我们做循环右移k位：新数组的第0个位置是原数组的第L-k个位置，所以： rotated[i] = temp[(i - (n-1) + L) % L] -> 当i=0，rotated[0]=temp[L-(n-1)]，即原数组的倒数第n-1个位置。 4. 将rotated数组按顺序放回最外层（顺序与提取时相同）。 但是，这种方法需要额外空间，而且逻辑稍显复杂。 方法三：直接计算旋转后的位置（更高效） 我们可以不提取整个环，而是直接计算最外层每个元素旋转后的位置。因为旋转90度后，每个元素的位置有固定的映射关系，但是内层元素不动，所以我们可以创建一个新的矩阵，先复制原矩阵，然后只修改最外层的元素。 步骤： 1. 创建一个新的n x n矩阵result，复制原矩阵。 2. 对于最外层的每个位置，计算它旋转90度后的位置，并将原矩阵的值赋给新矩阵的对应位置。 3. 注意：旋转90度后，原矩阵的位置(i,j)会旋转到新矩阵的(j, n-1-i)位置。但是，我们只旋转最外层，所以： 原矩阵最外层的位置包括： 上边：i=0, j=0..n-1 -> 旋转后：位置(j, n-1-0) = (j, n-1) -> 即新矩阵的右边一列（从下到上？不对，j从0到n-1，那么新矩阵的行j从0到n-1，列固定为n-1，所以是右边一列，从上到下？） 但是，我们旋转90度后，原矩阵的第一行会变成新矩阵的最后一列，而且顺序不变（即原(0,0)变成新矩阵(0,n-1)，原(0,1)变成新矩阵(1,n-1)，...，原(0,n-1)变成新矩阵(n-1,n-1)）-> 所以映射是：新矩阵(k, n-1) = 原矩阵(0,k) 其中k=0..n-1。 所以，对于上边的点(0,j)，旋转后位置为(j, n-1) 同理，右边的点(i, n-1)（i从0到n-1），旋转后位置为(n-1, n-1-i) -> 因为原矩阵(i,n-1)旋转后，行变成n-1，列变成n-1-i（因为旋转公式：(i,n-1) -> (n-1, n-1-i)）-> 所以变成新矩阵的最后一行（从右到左？） 下边的点(n-1,j)（j从n-1到0，但这里我们按顺序，j从0到n-1）旋转后位置为(j,0) -> 因为(n-1,j) -> (j, n-1-(n-1))=(j,0) -> 新矩阵的第一列（从上到下）？但是注意，原矩阵下边的一行，旋转后应该变成新矩阵的第一列，而且顺序是：原矩阵(n-1,0)变成新矩阵(0,0)，原矩阵(n-1,1)变成新矩阵(1,0)，...，原矩阵(n-1,n-1)变成新矩阵(n-1,0)）-> 所以这里j从0到n-1，那么新矩阵的位置是(j,0)，即第一列从上到下。 左边的点(i,0)（i从0到n-1）旋转后位置为(0, n-1-i) -> 因为(i,0) -> (0, n-1-i) -> 新矩阵的第一行（从右到左？）即原矩阵(0,0)旋转后到(0,n-1)位置，而原矩阵(n-1,0)旋转后到(0,0)位置？不对，根据公式，原矩阵(i,0)旋转后为(0, n-1-i)，所以当i=0时，位置(0,0)旋转后到(0,n-1)；当i=n-1时，位置(n-1,0)旋转后到(0,0)。所以新矩阵的第一行：从右到左是：原矩阵左边从上到下的顺序。 但是，这样直接赋值会覆盖，因为我们在修改新矩阵，所以可以同时进行。 然而，如果我们直接在新矩阵上赋值，那么原矩阵的值会被覆盖吗？我们创建了一个新矩阵，所以不会。 具体步骤： 创建一个新的矩阵result，大小n x n，初始化为原矩阵（或者我们可以先复制，然后只修改最外层，内层不变）。 然后，我们只修改最外层： 上边：原矩阵(0,j) -> 新矩阵(j, n-1) （j从0到n-1） 右边：原矩阵(i, n-1) -> 新矩阵(n-1, n-1-i) （i从0到n-1） 下边：原矩阵(n-1,j) -> 新矩阵(j,0) （j从0到n-1） 注意：这里下边我们按列从左到右（j从0到n-1）旋转后变成新矩阵的第一列从上到下（行号j，列0） 左边：原矩阵(i,0) -> 新矩阵(0, n-1-i) （i从0到n-1） 但是，注意：这样赋值，四个角会被重复赋值吗？不会，因为四个角分别属于上边和左边（左上角：上边和左边都包含，但是我们在上边赋值时已经赋值一次，在左边赋值时又赋值一次？）所以会覆盖。 例如，左上角(0,0)： 在上边：j=0 -> 新矩阵(0, n-1)位置（即右上角）赋值：值为原矩阵(0,0) 在左边：i=0 -> 新矩阵(0, n-1-0)=新矩阵(0,n-1)位置，又赋值一次（同一个位置，值相同）-> 没问题。 但是，右上角(0,n-1)： 上边：j=n-1 -> 新矩阵(n-1, n-1)位置（右下角）？不对，上边的映射：原(0,n-1) -> 新矩阵(n-1, n-1) [因为j=n-1] 右边：i=0 -> 新矩阵(n-1, n-1-0)=新矩阵(n-1, n-1) -> 所以右下角被赋值两次（值相同）-> 没问题。 但是，左下角(n-1,0)： 下边：j=0 -> 新矩阵(0,0)位置（左上角）赋值：值为原矩阵(n-1,0) 左边：i=n-1 -> 新矩阵(0, n-1-(n-1))=新矩阵(0,0)位置，又赋值一次（值相同）-> 没问题。 右下角(n-1,n-1)： 下边：j=n-1 -> 新矩阵(n-1,0)位置（左下角）赋值：值为原矩阵(n-1,n-1) 右边：i=n-1 -> 新矩阵(n-1, n-1-(n-1))=新矩阵(n-1,0)位置，又赋值一次（值相同）-> 没问题。 所以，四个角被赋值两次，但值相同，所以没关系。 但是，注意：我们这样赋值，新矩阵的内层元素并没有改变（因为复制了原矩阵，然后只修改了最外层），所以内层保持不变。 但是，这里有一个问题：我们赋值时，原矩阵的值可能被覆盖？因为我们创建了新矩阵，所以不会覆盖原矩阵的数据。但是，如果题目要求原地旋转，那么我们就不能创建新矩阵。不过，题目没有明确要求原地，所以我们可以用新矩阵。 然而，题目要求是“旋转n x n 01矩阵的最外层元素”，然后得到结果。所以我们可以返回新矩阵。 但是，如果要求原地旋转，那么我们需要使用临时变量或者交换。由于四个位置同时赋值，原地旋转会覆盖，所以我们需要保存四个位置的值？或者用临时数组保存最外层。 题目没有明确要求原地，所以我们可以选择创建新矩阵。 算法（创建新矩阵）： vector<vector<int>> rotateOuterLayer(vector<vector<int>>& matrix) { int n = matrix.size(); if (n == 0) return matrix; // 创建结果矩阵，复制原矩阵 vector<vector<int>> result = matrix; // 如果n==1，最外层只有一个元素，旋转后不变，直接返回。 if (n == 1) return result; // 旋转最外层 for (int j = 0; j < n; j++) { // 上边: (0,j) -> (j, n-1) result[j][n-1] = matrix[0][j]; } for (int i = 0; i < n; i++) { // 右边: (i, n-1) -> (n-1, n-1-i) result[n-1][n-1-i] = matrix[i][n-1]; } for (int j = 0; j < n; j++) { // 下边: (n-1,j) -> (j, 0) result[j][0] = matrix[n-1][j]; } for (int i = 0; i < n; i++) { // 左边: (i,0) -> (0, n-1-i) result[0][n-1-i] = matrix[i][0]; } return result; } 但是，我们测试一下2x2矩阵： 原矩阵： a b c d 新矩阵： 上边：j=0: result[0][1] = a -> 新矩阵(0,1)=a j=1: result[1][1] = b -> 新矩阵(1,1)=b 右边：i=0: result[1][1] = a -> 覆盖了b（这里不对，因为右边映射：原矩阵(0,1)旋转后应该是新矩阵(1,1)=b，但是这里我们右边赋值时，i=0对应原矩阵(0,1)=b，然后新矩阵(1,1)=b？不对，我们右边赋值时，取的是原矩阵(i,n-1)，即原矩阵的最后一列：i=0->(0,1)=b，i=1->(1,1)=d，所以右边赋值后： i=0: result[1][1] = b -> 覆盖了上边赋值的b（相同，没问题） i=1: result[1][0] = d -> 新矩阵(1,0)=d （注意：n-1-i=1-1=0，所以位置(1,0)） 下边：j=0: result[0][0] = c -> 原矩阵(n-1,0)=c，所以新矩阵(0,0)=c j=1: result[1][0] = d -> 覆盖了之前右边的赋值（d覆盖d，没问题） 左边：i=0: result[0][1] = a -> 覆盖了上边赋值的a（相同） i=1: result[0][0] = c -> 覆盖了下边赋值的c（相同） 所以最后新矩阵： (0,0): c （被左边赋值覆盖为c，但原本就是c） (0,1): a （被左边赋值覆盖为a，但原本就是a） (1,0): d （下边赋值覆盖为d） (1,1): b （右边赋值覆盖为b） 所以结果是： c a d b -> 和之前原地旋转的结果一致，即顺时针旋转90度。 但是，我们再看3x3矩阵： 原矩阵： 1 2 3 4 5 6 7 8 9 新矩阵： 上边：j=0->(0,0)旋转后到(0,2)=1 j=1->(0,1)旋转后到(1,2)=2 j=2->(0,2)旋转后到(2,2)=3 右边：i=0->(0,2)=3旋转后到(2,2)=3 -> 覆盖了上边赋值的3（相同） i=1->(1,2)=6旋转后到(2,1)=6 i=2->(2,2)=9旋转后到(2,0)=9 -> 注意：n-1-i=3-1-0=2? 不对，n=3，n-1=2，所以i=0: n-1-i=2; i=1: n-1-i=1; i=2: n-1-i=0 所以：右边赋值： i=0: result[2][2] = matrix[0][2]=3 i=1: result[2][1] = matrix[1][2]=6 i=2: result[2][0] = matrix[2][2]=9 下边：j=0->(2,0)=7旋转后到(0,0)=7 j=1->(2,1)=8旋转后到(1,0)=8 j=2->(2,2)=9旋转后到(2,0)=9 -> 覆盖了之前右边赋值的9（相同） 左边：i=0->(0,0)=1旋转后到(0,2)=1 -> 覆盖了上边赋值的1（相同） i=1->(1,0)=4旋转后到(0,1)=4 i=2->(2,0)=7旋转后到(0,0)=7 -> 覆盖了下边赋值的7（相同） 所以新矩阵： (0,0)=7 (0,1)=4 (0,2)=1 (1,0)=8 (1,1)=5 (1,2)=2 -> 注意，内层元素5和2没有改变？不对，我们只旋转最外层，内层元素5应该不变，但是这里(1,2)=2，而原矩阵(1,2)=6，旋转后应该变成？不对，我们看旋转后的矩阵： 旋转90度后，整个矩阵应该是： 7 4 1 8 5 2 9 6 3 但是，我们新矩阵中： 第一行：7,4,1 -> 正确 第二行：8,5,2 -> 正确（因为内层元素5不变，而(1,2)位置应该是2，原矩阵(0,1)=2，旋转后到(1,2)） 第三行：9,6,3 -> 但是我们新矩阵第三行： (2,0)=9 (2,1)=6 (2,2)=3 -> 正确 所以，为什么(1,2)位置是2？因为在旋转后，原矩阵(0,1)=2旋转后应该到(1,2)位置，而我们在上边部分已经赋值了：上边部分j=1时，将原矩阵(0,1)=2赋值给新矩阵(1,2)。所以内层元素5我们并没有改变（因为新矩阵是复制原矩阵，所以5保留在(1,1)位置）。 所以，这个方法是正确的。 但是，注意：在赋值过程中，有些位置被覆盖了，但由于覆盖的值和原值相同，所以不影响。 然而，如果我们使用原地旋转，那么就会出问题，因为我们在赋值时，原矩阵的值会被覆盖。例如，在赋值上边时，我们修改了新矩阵的右边一列，而右边一列在后续的右边赋值中需要用到原矩阵的右边一列。所以原地旋转时，我们需要临时保存。 题目没有要求原地，所以我们可以用新矩阵。 但是，题目说“旋转矩阵的最外层元素”，没有说是否原地，所以两种都可以。这里我们选择创建新矩阵。 但是，如果n很大，创建新矩阵空间开销大，原地旋转更好。原地旋转我们可以用临时数组保存最外层环，然后重新赋值。 原地旋转方法（使用临时数组保存环）： 步骤： 1. 提取最外层环（按顺序）到临时数组temp（长度为L=4*(n-1)）。 2. 将temp数组循环右移n-1位（或者左移？）得到rotated数组（实际上，我们可以不显式移动，而是直接按偏移量赋值）。 3. 将rotated数组按原来的顺序（即提取的顺序）重新赋值给最外层。 具体： 提取：按前面说的方法，顺序提取：上边（从左到右）、右边（从上到下）、下边（从右到左）、左边（从下到上）-> 注意，下边和左边是逆序提取的。 然后，循环右移n-1位：rotated[i] = temp[(i - (n-1) + L) % L] 然后，按原来提取的顺序（同样的顺序）放回去： 上边：从(0,0)到(0,n-1) -> 将rotated[0]到rotated[n-1]依次赋值 右边：从(1,n-1)到(n-2,n-1) -> 将rotated[n]到rotated[n+n-2-1]（即rotated[n]到rotated[2*n-2-1]）赋值 下边：从(n-1,n-1)到(n-1,0)（注意，这里放回去的时候，应该按从左到右放？但是提取时是从右到左，所以放回去也要从右到左？不对，我们提取下边时，从(n-1,n-1)提取到(n-1,0)，所以提取的顺序是：下边从右到左。那么放回去时，我们也要按照这个顺序（即从右到左）将rotated数组的相应部分赋值。但是，rotated数组的相应部分（下边部分）是连续的一段，我们按顺序放回去，那么下边就会从左到右？不对，我们提取时下边是逆序的（从右到左），那么rotated数组中的下边部分也是逆序的，所以放回去时，我们按顺序（从左到右）放到下边，那么下边就会是逆序的？所以我们需要调整。 实际上，提取和放回的顺序必须一致：提取时下边是从右到左，那么放回时也要从右到左（即从(n-1,n-1)到(n-1,0)）赋值，这样下边才会和rotated数组中的顺序一致。 所以，放回： idx = 0; // 上边：行0，列0到n-1 for (j=0; j<n; j++) { matrix[0][j] = rotated[idx++]; } // 右边：行1到n-2，列n-1 for (i=1; i<n-1; i++) { matrix[i][n-1] = rotated[idx++]; } // 下边：行n-1，列n-1到0（从右到左） for (j=n-1; j>=0; j--) { matrix[n-1][j] = rotated[idx++]; } // 左边：行n-2到1，列0（从下到上）-> 注意，提取时左边是从下到上（即从行n-1到1，但提取时我们已经跳过了(0,0)和(n-1,0)）？不对，提取时左边是从(n-1,0)到(1,0)（从下到上），所以放回时也要从(n-1,0)到(1,0)吗？但是我们已经提取了(n-1,0)（在下边）和(0,0)（在上边），所以提取左边时，我们只提取了(n-2,0)到(1,0)（即中间部分），所以放回时，我们也是从下到上：行n-2到1（即从n-2递减到1）？不对，提取时是从(n-1,0)开始提取，但是我们已经提取了下边和上边，所以左边提取的是从(n-2,0)到(1,0)（从上到下？）-> 提取时，左边部分：我们是从行n-1-1（即n-2）到行1（注意，行0和行n-1已经提取过），而且提取顺序是从行n-1-1（即n-2）开始，递减到1（即从下到上）。所以放回时，我们也要从下到上：行n-2到1（递减）赋值。 但是，这样很麻烦。而且，题目要求顺时针旋转90度，我们通过移动环，然后放回，需要保证放回的顺序和提取的顺序一致，这样环才能完整。 所以，我建议还是用新矩阵的方法，简单直观。 因此，我们选择新矩阵的方法。 注意：题目要求是01矩阵，但实际可以是任意整数，但无关紧要。 代码实现（C++）: 注意：如果n=0或1，直接返回。 但是，如果n=0，返回空矩阵；n=1，返回原矩阵。 另外，我们也可以不用四个循环，而用一个循环遍历最外层的每个位置，然后直接计算新位置。但是，最外层有4*(n-1)个点，四个角被重复计算（但赋值相同），所以也可以。 这里我们用四个循环，清晰。 代码： vector<vector<int>> rotateOuterLayer(vector<vector<int>>& mat) { int n = mat.size(); if (n == 0) return {}; vector<vector<int>> res = mat; // 复制原矩阵 // 如果n==1，直接返回 if (n == 1) return res; // 旋转最外层 // 上边 -> 右边 for (int j = 0; j < n; j++) { res[j][n-1] = mat[0][j]; } // 右边 -> 下边 for (int i = 0; i < n; i++) { res[n-1][n-1-i] = mat[i][n-1]; } // 下边 -> 左边 for (int j = 0; j < n; j++) { res[j][0] = mat[n-1][j]; } // 左边 -> 上边 for (int i = 0; i < n; i++) { res[0][n-1-i] = mat[i][0]; } return res; } 但是，我们测试一下3x3矩阵： 原矩阵： 1 2 3 4 5 6 7 8 9 新矩阵： 上边->右边： j=0: res[0][2]=1 j=1: res[1][2]=2 j=2: res[2][2]=3 右边->下边： i=0: res[2][2]=mat[0][2]=3 -> 覆盖3 i=1: res[2][1]=mat[1][2]=6 i=2: res[2][0]=mat[2][2]=9 下边->左边： j=0: res[0][0]=mat[2][0]=7 j=1: res[1][0]=mat[2][1]=8 j=2: res[2][0]=mat[2][2]=9 -> 覆盖9 左边->上边： i=0: res[0][2]=mat[0][0]=1 -> 覆盖1 i=1: res[0][1]=mat[1][0]=4 i=2: res[0][0]=mat[2][0]=7 -> 覆盖7 所以res矩阵： (0,0)=7 (0,1)=4 (0,2)=1 (1,0)=8 (1,1)=5 (1,2)=2 (2,0)=9 (2,1)=6 (2,2)=3 这就是顺时针旋转90度后的矩阵。 但是，注意：我们这里赋值时，有些位置被多次赋值，但最后被覆盖成正确的值。比如(0,0)先被下边->左边赋值7，然后被左边->上边赋值7（覆盖）；(0,2)先被上边->右边赋值1，然后被左边->上边赋值1（覆盖）；(2,0)先被右边->下边赋值9，然后被下边->左边赋值9（覆盖）；(2,2)先被上边->右边赋值3，然后被右边->下边赋值3（覆盖）。 所以，最终结果正确。 但是，我们也可以优化，避免覆盖，但这样写代码简洁。 因此，我们采用这种方法。 注意：题目要求是01矩阵，但实际是整数，所以没问题。 最后，返回新矩阵。 但是，题目要求“旋转n x n 01矩阵的最外层元素”，我们只旋转了最外层，内层保持不变（因为复制了原矩阵，内层没有修改）。 所以，内层元素不变。 我们测试一下3x3矩阵，内层元素5确实没有变。 所以，代码实现如下。 注意：如果矩阵为空，直接返回。 另外，如果题目要求原地旋转，那么我们可以用临时数组保存最外层，然后重新赋值，但这里我们按照新矩阵的方式。 如果题目要求原地，我们可以稍作修改：用临时数组保存最外层，然后按照映射关系赋值回原矩阵的最外层。但是，映射关系和新矩阵的方法一样。 不过，题目没有明确要求，我们就用新矩阵。 下面，我们写代码。</think>### 旋转矩阵的最外层元素（顺时针90度） 在C++中旋转一个n×n矩阵的最外层元素（顺时针90度）时，内层元素保持不变。核心思路是**仅处理矩阵的最外层边界**，通过坐标映射关系将每个元素移动到新位置。以下为详细实现和解释： #### 算法步骤 1. **复制原矩阵**：创建新矩阵`res`，复制原矩阵所有元素（保持内层不变）。 2. **旋转最外层**： - **上边 → 右边**：原矩阵位置`(0, j)` → 新位置`(j, n-1)` - **右边 → 下边**：原矩阵位置`(i, n-1)` → 新位置`(n-1, n-1-i)` - **下边 → 左边**：原矩阵位置`(n-1, j)` → 新位置`(j, 0)` - **左边 → 上边**：原矩阵位置`(i, 0)` → 新位置`(0, n-1-i)` 3. **边界处理**：当`n=0`或`n=1`时直接返回（无需旋转）。 #### C++代码实现 ```cpp #include <vector> using namespace std; vector<vector<int>> rotateOuterLayer(vector<vector<int>>& mat) { int n = mat.size(); if (n == 0) return {}; // 空矩阵直接返回 vector<vector<int>> res = mat; // 复制原矩阵 if (n == 1) return res; // 1x1矩阵无需旋转 // 旋转最外层 for (int j = 0; j < n; j++) res[j][n-1] = mat[0][j]; // 上边 → 右边 for (int i = 0; i < n; i++) res[n-1][n-1-i] = mat[i][n-1]; // 右边 → 下边 for (int j = 0; j < n; j++) res[j][0] = mat[n-1][j]; // 下边 → 左边 for (int i = 0; i < n; i++) res[0][n-1-i] = mat[i][0]; // 左边 → 上边 return res; } ``` #### 示例演示 - **输入矩阵**（3×3）： ``` [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ``` - **输出矩阵**（仅最外层旋转）： ``` [[7, 4, 1], [8, 5, 2], [9, 6, 3]] ``` - **内层元素`5`保持不变**。 - **旋转逻辑**： - 上边`[1,2,3]` → 右边`[1,2,3]`（位置变为最后一列） - 右边`[3,6,9]` → 下边`[9,6,3]`（位置变为最后一行，逆序） - 下边`[7,8,9]` → 左边`[7,8,9]`（位置变为第一列） - 左边`[1,4,7]` → 上边`[7,4,1]`（位置变为第一行，逆序） #### 复杂度分析 - **时间复杂度**：$O(n)$，每个最外层元素仅访问一次。 - **空间复杂度**：$O(n^2)$，存储新矩阵（若允许原地修改可优化为$O(1)$，需额外临时变量）。 #### 关键点 - **坐标映射**：旋转本质是坐标变换（原位置`(i,j)` → 新位置`(j, n-1-i)`）。 - **边界处理**：通过四个循环分别处理四条边，避免内层元素被修改[^1][^3]。 - **覆盖问题**：部分位置被多次赋值（如四个角），但最终值正确（覆盖值与原值相同）。 --- ### 相关问题 1. **如何在不使用额外空间的情况下原地旋转矩阵的最外层？** （提示：使用临时变量保存四个位置元素，循环交换[^2][^4]） 2. **若需逆时针旋转90度，应如何修改坐标映射关系？** （提示：新位置为`(n-1-j, i)`） 3. **如何处理非方阵（如m×n）的最外层旋转？** （提示：需调整边界条件，环的长度为$2(m+n-2)$） 4. **旋转后如何验证内层元素未被修改？** （提示：在代码中添加内层元素检查断言） [^1]: 矩阵旋转本质是坐标的特定转换和映射。 [^2]: 原地旋转需通过循环交换四个位置的元素。 [^3]: 矩阵宏观调度技巧可分层处理旋转操作。 [^4]: 分步覆盖赋值时需注意元素覆盖顺序。