如何在随机数数组中找到所有的相同数
在一个随机数数组中,如何找到任意两个或更多的相同数?
我能想到的方法是先对数组排序,然后再依次判断并找到相同的数.但对于巨大的数组(如大于100000),效率太差了.有没有更好的方法??
[解决办法]
排序的效率比较低，复杂度最起码是O(n^2)。你可以用个二维数组，记录随机数的值和出现的个数，复杂度就是O（n）.这是牺牲空间获取时间。
[解决办法]
无须预先对原始随机数组排序,让它们维持原来的随机次序,
而到用的时候,从数组一个一个地取出,这样保证随机,
同时,再把取出的数进行插入排序.
由于取出数后总是排序的,所以每取一个新的数,就可用二分法
检查该数是否已在这个序列中,如果未出现在此序列中,就加入,
否则,就表明此数已经用过,就应从数组中另取一个数来试.
