[LeetCode] 48. Rotate Image

轉自LeetCode

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

<Solution>

這題要將 n x n 的 2D matrix 順時鐘旋轉 90度

有兩種轉法

解法一

• 先以右上到左下的對角線為軸，交換元素

• 然後再以水平線為軸，上下交換元素

1  2  3      9  6  3      7  4  1

4  5  6  ->  8  5  2  ->  8  5  2

7  8  9      7  4  1      9  6  3

code 如下

	class Solution {
	public:
	void rotate(vector<vector<int>>& matrix) {
	const int n = matrix.size();
	const int sizeIdx = n - 1;
	//>step 1: axis is right-top to left-bottom line
	for(int r = 0; r < sizeIdx; r++) {
	for(int c = 0; c < (sizeIdx - r); c++) {
	swap(matrix[r][c], matrix[sizeIdx - c][sizeIdx - r]);
	}
	}
	//>step 2: axis is horizontal line
	int mid = n / 2;
	for(int r = 0; r < mid; r++) {
	for(int c = 0; c < n; c++) {
	swap(matrix[r][c], matrix[sizeIdx - r][c]);
	}
	}
	}
	};

view raw rotateImage_1.cpp hosted with ❤ by GitHub

解法二

• 以左上到右下的對秤線為軸，交換元素

• reverse 每個 row

1  2  3      1  4  7      7  4  1

4  5  6  ->  2  5  8  ->  8  5  2

7  8  9      3  6  9      9  6  3

code 如下

	class Solution {
	public:
	void rotate(vector<vector<int>>& matrix) {
	const int n = matrix.size();
	const int sizeIdx = n - 1;
	//> step 1. axis it left-top to right-bottom line
	for(int r = sizeIdx; r >= 0; r--) {
	for(int c = 0; c < r; c++) {
	swap(matrix[r][c], matrix[c][r]);
	}
	//> step 2. reverse each row
	reverse(matrix[r].begin(), matrix[r].end());
	}
	}
	};

view raw rotateImage_2.cpp hosted with ❤ by GitHub