我需要k在范围内随机选择元素0 to n-1.n最高可达10 ^ 9.并且k可以从1 to n-1.我可以在O(n)时间内通过对包含值的数组进行混洗0 to n-1并k从中选择第一个元素来完成此操作.但是当它k很小时,这种方法既有时间也有内存效率低下.这个问题有没有O(k)解决方案？
注意:所选k数字必须不同.
我在想一个解决方案.我能想到两种方法.设R是要返回的集合.
R.继续这样做,直到|R| = k.此过程需要sum(n/i) for n+1-k <= i <= n时间和O(k)空间.k元素.此过程需要O(n + k)时间和空间.因此,对于给定的k我可以在O(k)时间中选择优选的方法.