旋轉圖像
給定一個N×N的二維矩陣表示圖像,90度順時針旋轉圖像。
看個例子
算法1:
如上圖所示,設一個N階二維矩陣,則將矩陣從外向里可以分成N/2個圈,例如(1 2 3 4 8 12 16 15 14 13 9 5)這是最外邊的圈,設圈的維度是n(最外圈有n=N=4),而(6 7 11 10)這是里邊的一個圈(n=2), 旋轉90度之后,每個數字是按照順時針的方向移動了n-1個位置。
找到數字該去的位置:
pair<int, int> getNextPos(int i, int j, int top, int left, int down, int right){//(top, left) (down, right)標示這個圈的范圍,即左上角坐標和右下角坐標int n = down-top+1;//得到這個圈的維度int move = n-1;//轉過move個位置while(move--){if(i==top && j>=left && j<right)++j;else if(i>=top && i<down && j==right)++i;else if(i==down && j<=right && j>left)--j;else if(i<=down && i>top && j==left)--i;}return make_pair(i, j); }
旋轉過程:
由上圖可見,1到4的位置,4到16的位置,16到13的位置,13到1的位置,結束循環。接著數字2和數字3按照同樣的步驟,完成了整個圈的旋轉操作。
void rotate(vector<vector<int> > &matrix) {// write your code here//方法1:轉圈法,從外圈到里圈,設圈的維度是n,圖像旋轉90度后,數字順時針移動n-1個位置int circle = matrix.size()/2;//得到圈的個數int top=0, left=0, down=matrix.size()-1, right=matrix.size()-1;//最外圈的維度for(int cir=0; cir<circle; ++cir){int ttop = top+cir;int lleft = left+cir;int rright = right-cir;int ddown = down-cir;
//(ttop, lleft) (ddown, rright)標示這個圈for(int j=lleft; j<rright; ++j){pair<int, int> org = make_pair(ttop, j);//原始位置,如果再次到這個位置,說明交換完畢pair<int, int> cur = org;int cur_val = matrix[cur.first][cur.second];//當前數的值while(true){pair<int, int> _next = getNextPos(cur.first, cur.second, ttop, lleft, ddown, rright);swap(matrix[_next.first][_next.second], cur_val);if(_next==org) break;cur = _next;}}}
}
算法2:
通過兩次折疊,先上下對換,再根據對角線對換,即可得到目標圖像。
void rotate(vector<vector<int> > &matrix) {int n = matrix.size();for(int i=0; i<n/2; ++i)for(int j=0; j<n; ++j)swap(matrix[i][j], matrix[n-i-1][j]);//上下對換for(int i=0; i<n; ++i)for(int j=0; j<i; ++j)swap(matrix[i][j], matrix[j][i]);//主對角線兩側交換 }
?
題目鏈接:
http://www.lintcode.com/zh-cn/problem/rotate-image/
?