程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Rotate Image

leetcode筆記:Rotate Image

編輯:C++入門知識

leetcode筆記:Rotate Image


一.題目描述

You are given an n×n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?

二.題目分析

由於要求將圖像順時針旋轉90度,最簡單的做法就是畫個圖出來觀察旋轉90度之後的圖像的情況,經過分析可知,順時針旋轉90度就是將原來的圖像的最後一行作為第一列,倒數第二行作為第二列,因此類推,第一行作為最後一列。如果不考慮in-place條件,我們可以創建一個大小為n×n的一個二維數組來進行復制操作,然後將旋轉後的圖像拷貝回原來的圖像中。這種做法的時間復雜度為O(n^2),空間復雜度為O(n^2)

但是,題目希望能in-place進行,由於無論圖像進行什麼角度的選擇,左上角的點都可以看作坐標系的原點,因此,將一幅圖像抽象成3×3的情形,可以從中找出一些規律:

1 2 3
4 5 6
7 8 9

順時針旋轉90度之後的圖像的抽象即為:

7 4 1
8 5 2
9 6 3

可以歸納出一種等價的變換:

首先,將矩陣的每個元素沿著沿著主對角線進行交換;

1 2 3 — 1 4 7
4 5 6 -> 2 5 8
7 8 9 — 3 6 9

然後,每列的元素沿著水平中線對稱翻轉一次,在這裡,第一列和第三列關於第二列對稱,因此只需將一、三列元素對調,即可得到旋轉90度後的結果。

1 4 7 — 7 4 1
2 5 8 -> 8 5 2
3 6 9 — 9 6 3

三.示例代碼:

#include 
#include 
using namespace std;

class Solution
{
public:
    void turnRightImage(vector >& image)
    {
        int imaSize = image.size();
        // 主對角線以下的元素與主對角線上元素沿著主對角線垂直方向對換
        for (int i = 1; i < imaSize; i++)
        {
            for (int j = i - 1; j >= 0; j--)
                swap(image[i][j], image[j][i]);
        }
        for (int k = 0; k < imaSize / 2; k++)
        {
            for (int l = 0; l < imaSize; l++)
                swap(image[l][k], image[l][imaSize - k - 1]);
        }
    }
};

一個測試結果:

這裡寫圖片描述

四.小結

這道題要求in-place運算,其實對於此類要求,應該更多考慮轉換前後數據/矩陣的關系。根據以上的分析我們知道,將一張圖片進行順時針90度旋轉,可等價於將矩陣的每個元素沿著沿著主對角線進行交換,然後沿著水平中線翻轉一次,或者先將矩陣元素沿著水平中線翻轉一次,然後再沿對角線交換,這樣可以做到in-place運行,空間復雜度為O(1)

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved