首页 > 试题广场 >

像素翻转

[编程题]像素翻转

热度指数：31253 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现有一个NxN的矩阵，阶数为N，请编写一个算法将矩阵顺时针旋转90度并将其作为返回值。要求不使用缓存矩阵，保证N不大于500，元素不大于256，每个元素用int表示。

测试样例：

[[1,2,3],[4,5,6],[7,8,9]],3

返回：[[7,4,1],[8,5,2],[9,6,3]]

算法知识视频讲解

查看答案及解析

推荐

luochangan

思路：第一步：先将矩阵以次对角线互换（如果是逆时针则为主对角线）

第二步：交换第i行到第n-i-1行

上代码：

public class Transform {
     public static int[][] transformImage(int[][] mat, int n) {
        if (mat == null) {
           return null;
               }
    
         int temp = 0;
        for(int i=0;i<n-1;i++){
          for(int j=0;j<n-i-1;j++){
                 temp = mat[i][j];
                 mat[i][j] = mat[n-j-1][n-i-1];
                 mat[n-j-1][n-i-1] = temp; 
             }   
        }
         
         for(int i=0;i<(n/2);++i){
             for(int j=0;j<n;++j){
                 temp = mat[i][j];
                 mat[i][j] = mat[n-i-1][j];
                 mat[n-i-1][j] = temp;
             }
             
         }
         
         return mat;
         
     }
}

编辑于 2015-08-18 20:34:59 回复(7)

Python

华科平凡

Python one line solution

return zip(*mat[::-1])

编辑于 2018-08-26 21:31:44 回复(7)

Ron

import java.util.*;
/* 思路：逐层旋转，最外层向内，其中layer表示当前所处理的层，
每次都是n*n矩阵中可以形成方阵中的四个数进行旋转，
左->上，下->左，右->下，上->右的顺序，
在第一步之前先存储“上”中的值*/

public class Transform {
    public int[][] transformImage(int[][] mat, int n) {
        // write code here
    	for(int layer = 0;layer < n/2; layer++){
    		int first = layer;
    		int last = n-1-layer;
    		for(int i = first; i < last; i++){
    			int offset = i - first;
    			int top = mat[first][i];
    			//left -> top
    			mat[first][i] = mat[last - offset][first];
    			//bottom -> left
    			mat[last-offset][first] = mat[last][last-offset];
    			//right -> bottom
    			mat[last][last-offset] = mat[i][last];
    			//top -> right
    			mat[i][last] = top;
    		}
    	}
    	return mat;
    }
}

编辑于 2015-08-23 23:01:31 回复(3)

Aurora1

public int[][] transformImage(int[][] mat, int n) {

		for (int i = 0; i < n >> 1; i++) {
			for (int j = i; j < n - 1 - i; j++) {
				int k = mat[i][j];

				mat[i][j] = mat[n - 1 - j][i];
				mat[n - 1 - j][i] = mat[n - 1 - i][n - 1 - j];
				mat[n - 1 - i][n - 1 - j] = mat[j][n - 1 - i];
				mat[j][n - 1 - i] = k;
			}
		}

		return mat;
	}

编辑于 2016-04-03 17:11:17 回复(0)

drdr

别人的思路：
首先上下翻转，再按照主对角线翻转 

	1 2 3                 7 8 9            7 4 1



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



	7 8 9                 1 2 3            9 6 3

vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
        //上下交换
        for(int i = 0; i < n/2; ++i){
            for(int j = 0; j < n; ++j){
                swap(mat[i][j], mat[n-1-i][j]);
            }
        }
        //主对角线交换
        for(int i = 0; i < n; ++i){
            for(int j = i+1; j < n; ++j){
                swap(mat[i][j], mat[j][i]);
            }
        }
        return mat;
    }

编辑于 2017-08-15 17:33:05 回复(0)

树边红雨

vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
	// write code here
	int i,j,temp=0;
	for (i=0;i<n;i++)
	{
		for (j=0;j<n/2;j++)
		{
			temp=mat[i][j];
			mat[i][j]=mat[i][n-1-j];
			mat[i][n-1-j]=temp;
		}
	}
	for (i=0;i<n;i++)
	{
		for (j=0;j<n-i;j++)
		{
			temp=mat[i][j];
			mat[i][j]=mat[n-1-j][n-1-i];
			mat[n-1-j][n-1-i]=temp;
		}
	}
	return mat;
}

编辑于 2015-08-20 20:46:03 回复(0)

KidyCharon

class Transform {
public:
    vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
        // write code here
        //转置
        vector< vector<int> > a = mat;
        for(int i = 0; i < n; i++)
            for(int j = i; j < n; j++)
                swap(a[i][j], a[j][i]);
        // 左右镜像
        for(int i =0; i < n;i++)
            for(int j = 0; j < n/2; j++)
                swap(a[i][j], a[i][n-j-1]);
            
        return a;
    }
};

发表于 2018-12-04 19:43:48 回复(0)

Java

大鱼BigFish

import java.util.*;

public class Transform {

public int[][] transformImage(int[][] mat,int n)

{

//第一步：先将矩阵转置

//第二步：交换第i行到第n-i-1行总共3行，最高行序号2，毕竟序号从0计数

int r,c;//行列

int temp;

for(r=0;r<n;r++)

for(c=r+1;c<n;c++)

{

temp=mat[r][c];

mat[r][c]=mat[c][r];

mat[c][r]=temp;

}

for(r=0;r<n;r++)

for(c=0;c<n/2;c++)

{

temp=mat[r][c];

mat[r][c]=mat[r][n-c-1];

mat[r][n-c-1]=temp;

}

return mat;

}

发表于 2017-04-12 17:45:51 回复(0)

nomico271

1 2 3 7 4 1 4 5 6 --> 8 5 2 7 8 9 9 6 3
翻转90度，即将原二维数组的第一行转为数组2的最后一列，第二行变为第二列，依次类推。。。实现：建一个同大小的空二维数组，从最后一列开始，将原数组第一行复制到新数组最后一列，依次类推。代码如下：

public class Transform {
    public int[][] transformImage(int[][] mat, int n) {
        // write code here

        int[][] copymat = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                copymat[j][n-1-i] = mat[i][j];
            }
        }

        return copymat;
    }
}

发表于 2017-03-12 11:59:13 回复(2)

acidlychee

    public int[][] transformImage(int[][] mat, int n) {
        // write code here
        //对矩阵副对角线上的元素进行交换。
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int j = i+1; j < n; j++) {
                temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        
        //再将0~n-1列进行两两对称交换。
        int i = 0;
        int j = n-1;
        while (i < j){
            int k = 0;
            int temp = 0;
            while (k < n){
                temp = mat[k][i];
                mat[k][i] = mat[k][j];
                mat[k][j] = temp;
                k++;
            }
            ++i;
            --j;
        }
        return mat;
    }

发表于 2015-10-07 13:00:50 回复(1)

0pandas0

感觉这道题根本就不是旋转90度，根据给出来的示例来看只是矩阵的行列互换，

然后代码放进去果然通过了。

如果是顺时针旋转

1 2 3 7 4 1

4 5 6 =>8 5 2

7 8 9 9 6 3

逆时针旋转

1 2 3 9 6 3

4 5 6 =>8 5 2

7 8 9 7 4 1

vector<vector<int> > tranformImage(vector<vector<int> > mat, int n) {
    // write code here
    int i,j,t;
    for( i=0;i<n;i++)
    {
        for( j=i+1;j<n;j++)
        {
            t=mat[i][j];
            mat[i][j]=mat[j][i];
            mat[j][i]=t;
        }
            
    }
    return mat;
}

编辑于 2015-10-08 17:57:30 回复(6)

Continue

import java.util.*;

public class Transform {
    public int[][] transformImage(int[][] mat, int n) {
        // write code here
        int[][] a = new int[n][n];
		for (int j = 0; j < n; j++) {
			for (int i = n - 1; i >= 0; i--) {
				a[j][n - i - 1] = mat[i][j];
			}
		}
		return a;
    }
}

发表于 2016-03-03 19:55:55 回复(3)

Java

小风筝0010

import java.util.*;

public class Transform {
    public int[][] transformImage(int[][] mat, int n) {
       
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                res[i][j] = mat[n-j-1][i];
            }
        }
        return res;
    }
}

发表于 2017-03-14 22:07:00 回复(0)

半雨微凉

vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
	vector<vector<int>> vv(mat.begin(), mat.end());
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = n - 1, k = 0; j >= 0, k < n; j--, k++)
		{
			vv[i][k] = mat[j][i];
		}
	}

	return vv;
}

行变列，列变行

发表于 2019-09-04 09:06:48 回复(0)

C/C++

但求八月九月好运！

class Transform {
public:
    vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
        if(n<=1) return mat;
        for(int i=0;i<n-1;++i)
            for(int j=0;i+j<n-1;++j)
                swap(mat[i][j],mat[n-1-j][n-1-i]);
        for(int k=0;k<n/2;++k)
            swap(mat[k],mat[n-1-k]);
        return mat;
    }
};

发表于 2019-05-01 20:33:41 回复(0)

aud

import java.util.*;

public class Transform {
    // 顺时针旋转，先上下翻，在沿着对角线翻
    // 逆时针旋转，先沿对角线翻，再上下翻
    public int[][] transformImage(int[][] mat, int n) {
        // write code here
        // 上下翻转 mat[i][j] ==> mat[n-1-i][j]
        for(int i=0;i<n/2;i++)
        {
            for(int j=0;j<n;j++)
            {
                int a = mat[i][j];
                mat[i][j] = mat[n-1-i][j];
                mat[n-1-i][j] = a;
            }
        }
        // 沿着对角线翻转  mat[i][j] ==> mat[j][i]
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                int a = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = a;
            }
        }
        return mat;
    }
}

顺时针和逆时针都一样思路的翻转方法

发表于 2019-01-21 00:44:11 回复(0)

马什么梅呀

添加一个偏置量offset

先对外层做旋转：

再对内层做循环：

class Transform {
public:
    vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
        for(int layer = 0;layer<n/2;++layer){
            int first = layer;
            int last = n-1-layer;
            //对每个圈进行旋转
            for(int i = first;i<last;++i){
                int offset = i-first;//偏置量
                int top = mat[first][i];
                mat[first][i]=mat[last-offset][first];
                mat[last-offset][first] = mat[last][last-offset];
                mat[last][last-offset] = mat[i][last];
                mat[i][last] = top;
            }
        }
        return mat;
    }
};

发表于 2018-11-20 11:24:59 回复(0)

C/C++

jojo201802031701590

class Transform {
public:
vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {

vector<vector<int>> c=mat;vector< vector<int> > c(n, vector<int>(n));

for (int i = 0; i < n; i++)
for (int j = 0; j< n; j++)
c[j][n-i-1] = mat[i][j];
return c;
}
};

编辑于 2018-02-12 17:23:26 回复(1)

Java

itellu

public int[][] transformImage(int[][] mat, int n) {
    if(mat==null || n<2)
        return mat;

    int[][] result=new int[n][n];

    for(int i=0;i<n;i++){//列
        for(int j=0;j<n;j++){
            result[j][i]=mat[n-1-i][j];
        }
    }

    return result;
}

编辑于 2017-09-11 16:01:25 回复(0)

InGodWeTrust

import java.util.*;

public class Transform {
    public int[][] transformImage(int[][] mat, int n) {
        int arrNew[][]=new int[n][n];
        int num=n-1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                arrNew[i][j]=mat[num][i];
                num--;
            }
            num=n-1;
        }
        return arrNew;
    }
}

发表于 2017-07-17 11:06:31 回复(0)

C/C++

N.A.

class Transform {
public:
    vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
        // write code here
        for (int i=0;i<n/2;i++){
            for (int j=i;j<n-i-1;j++){
                int mid=mat[i][j];
                mat[i][j]=mat[n-j-1][i];
                mat[n-j-1][i]=mat[n-i-1][n-j-1];
                mat[n-i-1][n-j-1]=mat[j][n-i-1];
                mat[j][n-i-1]=mid;
            }
        }
        return mat;
    }
};

发表于 2017-06-11 21:14:57 回复(0)