Facebook Intern 面经

axieyanga 发表于 2017-5-18 12:41
我看地里这个题目出现很多。我把我的想法说一下，这是代码我创建了index 的 数组 存对应的位置， 从最后开 ...

这个复杂度不是O(k)哦，initialize的时候已经O(m*n)
另：题目的m是雷的个数，这里是矩阵行数

你的思路是对的，但是不需要一个长度为m*n的数组来记录这个置换。用一个map就够了
不嫌弃的话看下楼上我的代码吧

因为我初始化的matrix 是boolean type 的存不了index.
你其实是把matrix当成缓存，最后ｋ　个位置存放ｂｏｏｍ　的　ｉｎｄｅｘ

补充内容 (2017-5-19 04:47):
忽略上面的话，你是对的。确实不需要开另外的ａｒｒａｙ

axieyanga 发表于 2017-5-18 12:41
我看地里这个题目出现很多。我把我的想法说一下，这是代码我创建了index 的 数组 存对应的位置， 从最后开 ...

如果不detect是否有两个mine随机出来位置重叠的话， 算出来的并不随机吧。 你的初始状态并不随机。如果我把K个Mine一开始放到最后，跟放在最前面是不一样的

求问 reservior sampling是什么意思？ 感谢

axieyanga 发表于 2017-5-18 12:41
我看地里这个题目出现很多。我把我的想法说一下，这是代码我创建了index 的 数组 存对应的位置， 从最后开 ...

还是不太懂 假设我们一共有n个数字 resevoir的大小是k 那我们就从k+1 ... n这些数开始generate random number
为什么可以直接从0..kgenerate 呢

dokolo 发表于 2016-11-15 11:51
我的想法是，从[0,hw-1]中随机一个数，如果这个数不是hw-1，那么用一个hashtable记下来这个位置应该是对应h ...

楼主这个完全不是resevoir sampling啊 能不能解释下为啥是对的呢

n个球取K个，每次取出来一个，取K次