某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一道题挺像
相关推荐
滴滴公司福利 672人发布 点赞 评论 收藏
分享
为生活添砖加瓦：都这么多双非大佬拿了超一线大厂吗
投递快手等公司10个岗位 点赞 评论 收藏
分享
04-25 21:06
门头沟学院 后端 
爱吃肉的伊登在写日记：好棒，27届简历能做成这个样子，但是第一个项目感觉cover住难度还是不小的，特别是二面的时候肯定要对分布式系统设计这一块儿有高出正常面试者的水平才行 点赞 评论 收藏
分享