如何將M×N矩陣180度旋轉到位？

Question

我在這裏看到了幾個問題，並不完全回答我的問題。我試圖做一些經常在面試問題中使用的經典矩陣旋轉問題的翻譯。我沒有關注方矩陣，而是對M×N矩陣感興趣。

對於輸入矩陣

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矩陣（尚未測試更高維矩陣），但我似乎在代碼中出現了一處錯誤，導致最內層元素保持未修剪狀態。

在行for(size_t j = 0; j <= n/2; ++j) {，我試着將停止條件調整爲幾件事情，包括j < (n+1)/2;和j < (n-1)/2;，但它仍然是一樣的。

有人可以解釋我的算法出錯了嗎？

Answer 1

當行數爲奇數時，您不會照顧中線。

此外，您交換位於中間列（當列號爲奇數時）的元素兩次。您可以檢查是否m是奇數與位按 - 與1.

以下是一個更簡單的方法來項目交換值是上面介紹，你甚至不必關心在這種情況下的中間列。

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]); 
} 

Answer 2

我會使用鏡X然後鏡ý或反之亦然。它適用於任何分辨率（偶數/奇數）並且安全。所以先交換所有行，然後交換所有列（反之亦然）。這裏有一些代碼。

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;i++) { 
    for(size_t j=0,k=n-1;j<k;j++,k--) { 
     std::swap(v[i][j],v[i][k]); 
    } 
    } 

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

Answer 3

一個pythonish方式（不到位）：

d = (1, 2, 3), (4, 5, 6), (7, 8, 9), (1, 2, 3) 

[r[::-1] for r in d[::-1]]