某top大厂提前批三面算法题
给一个n*m的矩阵（用一维数组表示），要求原地转置，空间复杂度要求O(1)
怎么解？
#关于提前批我想问#
2023-08-04 19:52 已编辑 门头沟学院 golang
关注
全部评论
Creed_
中山大学 C++
考虑一维矩阵的转置的本质，其实就是对于一个长度为n*m的排列应用一个置换P。考虑给定一个排列和一个转置，能否使用O(1)的空间对该排列应用转置，感觉不太好做，因为需要再遍历置换环的时候标记一下哪些位置被遍历过了，即需要用到一个vis数组，但这样会导致用到额外的空间开销。考虑把vis数组偷偷藏到原数组中，比如把a[x]=-a[x]来标识visited，或者把某个高二进制位改为1来标识。
不想说话的番茄
南京大学 算法工程师
写了一种只适用于原矩阵行数小于列数的情况。。。
kuan525
武汉轻工大学 golang
如果数据范围有明确指出，或许可以通过顺序遍历 -＞ 找路径 -＞打tag(比如取负数或者全部加100000000……)。类似于bfs中flood fill思想。
闲鱼一个
浙江大学 算法工程师
我也遇到类似了，但放宽了空间复杂度，虽然easy，a了也不影响挂啊
FWFJHLZ
浙江大学 算法工程师
我感觉没法不用额外空间啊
怎么还不发offer
四川大学 算法工程师
直接交换数值应该就行吧，原有的矩阵不算额外空间
升维升维升维度
门头沟学院 深度学习
m
油沫offer
北京邮电大学 Java
先上下折叠再对角线翻转能不能实现
MyriZzz
蚌埠坦克学院 算法工程师
leetcode原题也没要求O(1)空间，且整个讨论区都没有一个O(1)的解法，基本证明这题没办法O(1)
kuan525
武汉轻工大学 golang
有没有数据范围呢
有菜又菜
门头沟学院 安全工程师
字节？
无望守候
西南交通大学 安卓
直接转置呗，
牛客网用户12138837号
门头沟学院 Java
和hot100一道题挺像
相关推荐
06-24 15:30
门头沟学院 硬件开发 
公涤生：那是因为你只是实习啊，没人会对你有什么期待，也不会有太多考核。就好比你去上兴趣班，纯兴趣，不考试比赛，跟你上学比当然轻松很多。 点赞 评论 收藏
分享
05-07 19:59
武汉理工大学 Web前端 
点赞 评论 收藏
分享
06-24 19:00
山西大学 测试工程师 点赞 评论 收藏
分享