我有200个已排序的正整数数组(其中一些含有超过一百万个数字)。我需要找到在每个数组中都存在的第一个数字。你有什么建议吗?
我有200个已排序的正整数数组(其中一些含有超过一百万个数字)。我需要找到在每个数组中都存在的第一个数字。你有什么建议吗?
编辑:代码示例:
while n < len(data):
item = data[n][indices[n]]
if item < reference:
indices[n] += 1
elif item == reference:
n += 1
elif item > reference:
reference = item
n = 0
print reference
您可以对数组执行k路合并,并检查出现k
次的第一个元素。
另一种方法是创建直方图,并选择在直方图中出现k
次的第一个元素。在Java中,可以通过Map<Element,Integer>
轻松实现直方图。
这两种解决方案都是O(kn)
,其中k
是数组的数量,n
是平均数组大小,因此它基本上是输入大小的线性。
Arrays.binarySearch()
- Edwin Dalorzo