一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1199|回复: 21
收起左侧

[算法题] 旋转一个N*N的矩阵,不准开辟新空间

[复制链接] |试试Instant~ |关注本帖
MTC 发表于 2014-11-5 21:42:28 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
有没有什么好方法?逐层向里那个我感觉有点难理解,很难面试的时候立马写出来
daihao0310 发表于 2014-11-5 23:14:31 | 显示全部楼层
建议楼主可以看一下Cracking the Code Interview这本书,上面对这道题有比较详细的算法描述。
回复 支持 1 反对 0

使用道具 举报

zombiecry 发表于 2014-11-5 21:56:25 | 显示全部楼层
本帖最后由 zombiecry 于 2014-11-5 21:57 编辑

是LeetCode上面那个旋转90度的题目吗?
我的方法很好理解:
旋转90度的结果跟求转置很像。区别是第一行变成最后一列而不是第一列。
所以可以先给这个矩阵转置。然后把前n/2列逐次和后n/2列交换就行了。
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-11-5 22:09:27 | 显示全部楼层
zombiecry 发表于 2014-11-5 21:56
是LeetCode上面那个旋转90度的题目吗?
我的方法很好理解:
旋转90度的结果跟求转置很像。区别是第一行变 ...

对,就是那道,大牛贴一下code吧
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-11-6 00:38:10 | 显示全部楼层
不开辟新空间能做到? 起码也要有一个O(1)的新空间吧, swap的时候不用一个变量,怎么swap?
回复 支持 反对

使用道具 举报

evensong 发表于 2014-11-6 01:03:46 | 显示全部楼层
如果连循环时候的变量都不能设立,我也没着了。
不然,可以用异或交换两个变量,这样不用开辟额外空间。
异或交换之前,要判断当前行和列是否相等,以及值是否相等。
回复 支持 反对

使用道具 举报

ysyyork 发表于 2014-11-6 01:17:34 | 显示全部楼层
本帖最后由 ysyyork 于 2014-11-6 01:18 编辑

先沿西南到东北的对角线翻转一次,在沿垂直中线翻转一次
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-11-6 09:41:45 | 显示全部楼层
ysyyork 发表于 2014-11-6 01:17
先沿西南到东北的对角线翻转一次,在沿垂直中线翻转一次

能给个详细的link或者code吗?
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-11-6 09:47:44 | 显示全部楼层
ysyyork 发表于 2014-11-6 01:17
先沿西南到东北的对角线翻转一次,在沿垂直中线翻转一次

垂直中线是哪一条?
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-11-6 09:54:11 | 显示全部楼层
evensong 发表于 2014-11-6 01:03
如果连循环时候的变量都不能设立,我也没着了。
不然,可以用异或交换两个变量,这样不用开辟额外空间。
...

可以交换的,能详细点说吗
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-11-6 09:54:36 | 显示全部楼层
daihao0310 发表于 2014-11-5 23:14
建议楼主可以看一下Cracking the Code Interview这本书,上面对这道题有比较详细的算法描述。

哥,我看了那个解法,太复杂了根本不好理解啊
回复 支持 反对

使用道具 举报

ysyyork 发表于 2014-11-6 10:23:14 | 显示全部楼层
MTC 发表于 2014-11-6 09:41
能给个详细的link或者code吗?

public void rotate(int[][] matrix) {
        //先对角线翻转一次,在沿中线翻转
        int len = matrix.length;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < len - i; j++) {
                int temp = matrix[j];
                matrix[j] = matrix[len-1-j][len-1-i];
                matrix[len-1-j][len-1-i] = temp;
            }
        
        for (int i = 0; i < len / 2; i++)
            for (int j = 0; j < len; j++) {
                int temp = matrix[j];
                matrix[j] = matrix[len-1-i][j];
                matrix[len-1-i][j] = temp;
            }
    }

行的中线。如果你有3行——0,1,2——那就是行1
回复 支持 反对

使用道具 举报

evensong 发表于 2014-11-6 10:57:27 | 显示全部楼层
MTC 发表于 2014-11-6 09:54
可以交换的,能详细点说吗

if (a != b)
        a ^= b, b^=a, a^=b;
回复 支持 反对

使用道具 举报

zombiecry 发表于 2014-11-7 14:20:21 | 显示全部楼层
本帖最后由 zombiecry 于 2014-11-7 14:21 编辑
zombiecry 发表于 2014-11-5 21:56
是LeetCode上面那个旋转90度的题目吗?
我的方法很好理解:
旋转90度的结果跟求转置很像。区别是第一行变 ...

    void rotate(vector<vector<int> > &matrix) {
        int n=matrix.size();
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                swap(matrix[j],matrix[j]);
            }
        }
        for(int j=0;j<n/2;j++){
            for(int i=0;i<n;i++){
                swap(matrix[j],matrix[n-1-j]);
            }
        }
    }
如果O(1)空间都不能开辟的话,就用位运算代替swap吧,具体可以搜一下。
回复 支持 反对

使用道具 举报

285845348 发表于 2014-11-7 14:56:42 | 显示全部楼层
来个python的

class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of lists of integers
    def rotate(self, matrix):
        l = len(matrix)
        for i in xrange(0, l - 1):
            for j in xrange(l - 1 - i):
                matrix[j], matrix[l-1-j][l-1-i] = matrix[l-1-j][l-1-i], matrix[j]
        i, j = 0, l - 1
        while i < j:
            matrix, matrix[j] = matrix[j], matrix
            i, j = i + 1, j - 1
        return matrix


补充内容 (2014-11-7 12:13):
沿dediag转置,交换行(比换列快很多)
回复 支持 反对

使用道具 举报

南若冲 发表于 2014-11-7 16:55:37 | 显示全部楼层
给个C++的
T为0时表示左右翻转,为1时表示上下翻转。

#include <iostream>
using namespace std;

int main ()
{
        int A[201][201];
        int M, N, T;
        cin >> M >> N >>T;
        for (int i = 0; i < M; i++)
        {
                for (int j = 0; j < N; j++)
                        cin >> A[i][j];
        }
        if ( T == 1)
        {
                for (int i = M - 1; i >= 0; i--)
                {
                        for (int j = 0; j < N; j++)
                                cout << A[i][j] << ' ';       
                        cout << endl;
                }
        }
        else
        {
                for (int i = 0; i < M; i++)
                {
                        for (int j = N -1 ; j >= 0; j--)
                                cout << A[i][j] << ' ';               
                        cout << endl;
                }
        }
        //while (1);
        return 0;
}






回复 支持 反对

使用道具 举报

双尾怪手 发表于 2014-11-7 22:44:40 | 显示全部楼层
想到一个也许可行的吧,因为是N*N,可研主对角线分成两部分,假设上半部分是Aij,下半部分是Aji,首先上半部分减下半部分,上半部分变成Aij-Aji,下半部分保留;下半部分与上半部分相加,上半部分保留Aij-Aji,下半部分变为Aji+(Aij-Aji)=Aij;上半部分取相反数并且与下半部分相加,上半部分变为Aji,得到转置。
回复 支持 反对

使用道具 举报

双尾怪手 发表于 2014-11-7 22:46:54 | 显示全部楼层
双尾怪手 发表于 2014-11-7 22:44
想到一个也许可行的吧,因为是N*N,可研主对角线分成两部分,假设上半部分是Aij,下半部分是Aji,首先上半 ...

转置以后可以交换列就得到旋转的结果了?
回复 支持 反对

使用道具 举报

双尾怪手 发表于 2014-11-7 22:47:01 | 显示全部楼层
双尾怪手 发表于 2014-11-7 22:44
想到一个也许可行的吧,因为是N*N,可研主对角线分成两部分,假设上半部分是Aij,下半部分是Aji,首先上半 ...

转置以后可以交换列就得到旋转的结果了
回复 支持 反对

使用道具 举报

鱼吃鱼翅 发表于 2014-11-8 03:51:23 | 显示全部楼层
kelvinzhong 发表于 2014-11-6 00:38
不开辟新空间能做到? 起码也要有一个O(1)的新空间吧, swap的时候不用一个变量,怎么swap?

可以用xor实现in place的swap
int a = 6, b = 8;
a = a ^ b;
b = a ^ b;
a = a ^ b;
这样a=8,b=6了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表