U ber电面水过

U ber 电面是匹兹堡打过来
问题简单，给一个矩阵大小M*N，和一个小于矩阵总元素个数的K，返回一个M*N的矩阵，要求里面有K个1，剩下的全是0

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

么提示都不行
过了几天HR打电话过来居然反馈还可以。。两周后onsite

没有看懂你的这句话：“Rand()%(M*N), 如果<K, 那么就将矩阵中对应位置设为1”。我想能否这么做：（1）Random(m*n - 1).nextInt（）,然后把这个随机数存到set里面，（2）然后重复nextInt，把这个随机数放set里面(有可能这次随机数与之前重复），直到set的size==k就停下。（3）根据set里面元素把矩阵对应位置值设成1或者0.

下面方法有帮助么？
1. 如果k接近M*N，应该反过来全初始化为1，然后求0的位置
2. 如果M*N足够小，而且假设产生随即数的代价比较高，那么可以一次性产生一个超大随机数，然后不断求M*N的mod来产生位置，虽然时间复杂度上好像没有变化

恭喜啊，看来估计是简历够硬。

所以原来矩阵的数字是没用吗

可不可以直接生成1～mn 然后shuffle一下取前k个

楼主选的是什么组？ 我都等了N周了还是没收到ONSITE邀请

zorrowei 发表于 2019-2-15 07:13
没有看懂你的这句话：“Rand()%(M*N), 如果

是的。就是你这个思路，重复这一个过程直到矩阵中填入K个1，这个是最直接的做法。

hpplayer 发表于 2019-2-15 07:56
楼主选的是什么组？ 我都等了N周了还是没收到ONSITE邀请

选的ATG无人车组

pandami 发表于 2019-2-15 06:41
所以原来矩阵的数字是没用吗

原来的矩阵可以认为全部为0

pandami 发表于 2019-2-15 06:43
可不可以直接生成1～mn 然后shuffle一下取前k个

你这方法应该可以的，其实Reservoir Sampling类似的思路。