LeetCode Rotate Image旋转图像

Rotate Image

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?

其实题目更好理解为旋转一个矩阵的下标90°。实际问题实际分析，这里不用图形学的选择矩阵的计算方法了。

关键是要把下标计算好，原矩阵的数值应该对应到新的旋转矩阵的那个位置，设计好公式就很容易计算了。

有图好理解，矩阵如下图：

有两个思路：

1 原矩阵计算出各个数值在新矩阵中的位置，然后一步到位转换成新的旋转矩阵

2 原矩阵到转置矩阵是很容易计算的，那么从转置矩阵到选择矩阵就只需要reverse每行的元素就可。

个人觉得还是第二种方法更为清晰一点。

思路一程序：

出处：http://discuss.leetcode.com/questions/226/rotate-image

void rotate(vector<vector<int> > &matrix) {
		int n = matrix.size();
		for(int i = 0; i < n/2; ++i)
			for(int j = i; j < n-1-i; ++j){
				int t = matrix[i][j];
				matrix[i][j] = matrix[n-1-j][i];
				matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
				matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
				matrix[j][n-1-i] = t;
			}
	}

思路二程序：

void rotate(vector<vector<int> > &matrix) {
		for(int i=0,n=matrix.size();i<n;++i){
			for(int j=i+1;j<n;++j)
				swap(matrix[i][j],matrix[j][i]);
			reverse(matrix[i].begin(),matrix[i].end());        
		}
	}

 updat:

//这样设计希望下标清晰点，不用计算的那么辛苦
	void rotate3(vector<vector<int> > &matrix) {
		int n = matrix.size();
		int i = 0, j = n-1;
		for (;i < j; i++, j--)
		{

			int forward = i, backward = j;
			while (forward < j)
			{
				int t = matrix[i][forward];
				matrix[i][forward] = matrix[backward][i];
				matrix[backward][i] = matrix[j][backward];
				matrix[j][backward] = matrix[forward][j];
				matrix[forward][j] = t;
				forward++; backward--;
			}
		}
	}

 

 最简洁的程序了

//2014-1-27 update
	void rotate(vector<vector<int> > &matrix) 
	{
		for (int i = 0, j = matrix.size()-1; i < j; i++, j--)
		{
			for (int k = i, d = j; k < j; k++, d--)
			{
				int t = matrix[i][k];
				matrix[i][k] = matrix[d][i];
				matrix[d][i] = matrix[j][d];
				matrix[j][d] = matrix[k][j];
				matrix[k][j] = t;
			}
		}
	}