首页 > 试题广场 > 像素翻转
[编程题]像素翻转
  • 热度指数:28932 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

有一副由NxN矩阵表示的图像,这里每个像素用一个int表示,请编写一个算法,在不占用额外内存空间的情况下(即不使用缓存矩阵),将图像顺时针旋转90度。

给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于500,图像元素小于等于256。

测试样例:
[[1,2,3],[4,5,6],[7,8,9]],3
返回:[[7,4,1],[8,5,2],[9,6,3]]
推荐
思路:第一步:先将矩阵以次对角线互换 (如果是逆时针则为主对角线)
           第二步:交换第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)
首先上下翻转,再按照主对角线翻转
 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
如果是逆时针翻转则先翻主对角线,再上下翻转
	
classTransform {
public:
    vector<vector<int> > transformImage(vector<vector<int> > mat, intn) {
        // write code here
        inta;
        for(inti=0;i<n/2;i++)
            {
            for(intj=0;j<n;j++)
                {
                a=mat[i][j];
                mat[i][j]=mat[n-i-1][j];
                mat[n-i-1][j]=a;
            }
        }
        for(inti=0;i<n;i++)
            {
            for(intj=0;j<i;j++)
                {
                a=mat[i][j];
                mat[i][j]=mat[j][i];
                mat[j][i]=a;
            }
        }
        returnmat;
    }
};

编辑于 2016-08-13 23:54:27 回复(5)
思路:
把矩阵想成一个洋葱,一圈包着一圈,外一圈每一条边比里一圈每一条边长度多2,每一条边只有边长度-1个元素需要覆盖另一条边的对应元素,因为每一条边与相邻两条边相交,一条边第一个元素旋转90度其实覆盖的是这一条边的最后一个元素,也是相邻边的第一个元素。
        int temp;
        for(int i=0;i<n/2;i++){
            for(int j=i;j<n-1-i;j++){
                temp = 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]=temp;
            }

        }
        return mat;

发表于 2015-08-08 18:56:06 回复(18)

Python one line solution

return zip(*mat[::-1])
编辑于 2018-08-26 21:31:44 回复(6)
Ron头像 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)
别人的思路:
首先上下翻转,再按照主对角线翻转 
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)
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)
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)
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)

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 回复(0)
    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)
感觉这道题根本就不是旋转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)
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)
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)
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头像 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)
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)
 
添加一个偏置量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)
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)
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)