如何将 M x N 矩阵原地旋转 180 度? [英] How do I rotate M x N matrix 180 degrees in place?

问题描述

我在这里看到了几个不能完全回答我的问题的问题.我正在尝试对面试问题中经常使用的经典矩阵旋转问题进行演绎.我对 M x N 矩阵感兴趣，而不是关注方阵.

I've seen several questions here that don't quite answer my question. I'm trying to do a rendition of the classic matrix rotation question used so often in interview questions. Instead of focusing on the square matrix, I'm interested in M x N matrices.

对于输入矩阵

1 2 3
4 5 6
7 8 9
1 2 3

我想把矩阵转换成

3 2 1
9 8 7
6 5 4
3 2 1

这是我写的代码:

#include <iostream>
#include <vector>
#include <algorithm>

void do_swaps(int& a, int& b, int& c, int& d) {
  std::swap(a, b);
  std::swap(c, d);
}

void rotate(std::vector<std::vector<int>>& v) {
  size_t m = v.size();
  size_t n = v[0].size();

  for(size_t i = 0; i < m/2; ++i) {
    for(size_t j = 0; j <= n/2; ++j) {
      do_swaps(v[i][j], v[m-i-1][n-j-1], v[m-j-1][i], v[j][n-i-1]);
    }
  }
}

void print(const std::vector<std::vector<int>>& v) {
  size_t m = v.size();
  size_t n = v[0].size();

  for(size_t i = 0; i < m; ++i) {
    for(size_t j = 0; j < n; ++j) {
      std::cout << v[i][j] << ' ';
    }
    std::cout << '\n';
  }
}


int main() {
  std::vector<std::vector<int>> m{{1,2,3}, {4,5,6}, {7,8,9}, {1, 2, 3}};
  std::cout << "Before: \n";
  print(m);
  rotate(m);
  std::cout << "\nAfter: \n";
  print(m);
}

这是我的输出:

Before: 
1 2 3 
4 5 6 
7 8 9 
1 2 3 

After: 
3 2 1 
9 5 7 
6 8 4 
3 2 1 

我的代码适用于 3 x 3 矩阵(尚未测试高维矩阵)，但我的代码中似乎有一个错误导致最内部的元素保持未交换.

My code works for 3 x 3 matrices (haven't tested higher dimensional matrices), but I seem to have an off by one error in my code causing the inner-most elements to remain unswapped.

在 for(size_t j = 0; j <= n/2; ++j) { 行中，我尝试将停止条件调整为包括 j 在内的几项内容<(n+1)/2; 和 j <(n-1)/2;，但它保持不变.

In the line for(size_t j = 0; j <= n/2; ++j) {, I've tried adjusting the stop condition to several things including j < (n+1)/2; and j < (n-1)/2;, but it remains the same.

有人能解释一下我的算法哪里出错了吗?

Can someone explain where I've gone wrong in my algorithm?

推荐答案

当行数为奇数时，您不考虑中间行.

You don't take care of middle line in case when lines number is odd.

此外，您将位于中间列(当列数为奇数时)上的元素交换两次.您可以检查 m 是否为按位和 1 的奇数.

Further, you swap elements that lie on the middle column (when columns number is odd) twice. You can check if m is odd with a bitwise-and with 1.

下面是一种更简单的投影交换值的方法，在这种情况下，您甚至不必关心中间的列.

The following is an easier way to project swapped values is presented above and you don't even have to care about the middle column in this case.

void rotate(std::vector<std::vector<int>>& v) {
    size_t m = v.size();
    size_t n = v[0].size();

    for (size_t i = 0; i < m / 2; ++i)
    {
        for (size_t j = 0; j < n; ++j)
            std::swap(v[i][j], v[m - i - 1][n - j - 1]);
    }
    if (m&1)
    for (size_t i = 0; i< n/2; ++i)
        std::swap(v[m/2][i], v[m/2][n-i-1]);
}

这篇关于如何将 M x N 矩阵原地旋转 180 度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！