给定一个包含 43 亿个 32 位整数的文件，我们如何找到至少出现过两次的数字？

Question

我为此想出了分而治之的算法。只是想知道这是否有效？

第一个 mid 是从整数范围计算的，即 (0+(1<<32-1))>>1 然后应用这个想法：从 start 到 mid 或从 mid 到 end 的数字范围总是小于我们要考虑的数字，因为我们正在考虑十亿个数字，并且肯定会有一些数字将被重复，因为与十亿个数字相比，32 位整数的范围要小得多。

def get_duplicate(input, start, end):  
  while True:
    mid = (start >> 1) + end - (end >> 1)
    less_to_mid = 0
    more_to_mid = 0
    equal_to_mid = 0
    for data in input:
        data = int(data, 16)
        if data < mid:
            less_to_mid += 1
        elif data == mid:
            equal_to_mid += 1
        else:
            more_to_mid += 1
    if equal_to_mid > 1:
        return mid
    elif mid-start < less_to_mid:
        end = mid-1
    elif end-mid < more_to_mid:
        start = mid+1

with open("codes\output.txt", 'r+') as f:
  content = f.read().split()
  print(get_duplicate(content, 0, 1<<32-1))

我知道我们可以使用位数组，但我只是想了解您对此解决方案的看法以及实施是否有问题。

Answer 1

2^32 位内存对于现代系统来说没什么特别的。所以你必须使用 bitset，这个数据结构每个数字只需要一个位，所有现代语言都有一个实现。想法是这样的——你只需要记住是否已经看到了一个数字：

void print_twice_seen (Iterator &it)//iterates through all numbers
{
  std::bitset< (1L<<32) > seen;//bitset for 2^32 elements, assume 64bit system

  while(it.hasNext()){
       unsigned int val=it.next();//return current element and move the iterator
       if(seen[val])
           std::cout<<"Seen at least twice: "<<val<<std::endl;
       else
           seen.set(val, true);//remember as seen
  }
}

Answer 2

你的方法没问题。但您可能需要多次阅读输入内容才能找到答案。

这里有一个变体，它可以让你用很少的内存找到重复项，但你只需要读取输入两次。

将整数数组 A[65536] 初始化为零。
一个一个读出数字。每读取一个数字x，就在A[x mod 65536]中加上1。
阅读结束时，至少会有一个i使得A[i]严格大于65536。这是因为 65536 * 63356 < 4.3 billion。假设 A[i0] 大于 65536。
将数组 A 清零。
再读一遍数字，但这次只看那些 x 满足 x mod 65536 = i0 的数字。对于每个这样的 x，将 1 添加到 A[x / 65536]。
阅读结束时，至少会有一个j使得A[j]严格大于1。那么数字65536 * j + i0就是最终答案

给定一个包含 43 亿个 32 位整数的文件，我们如何找到至少出现过两次的数字？

Given a file containing 4.30 billion 32-bit integers, how can we find a number, which has appeared at least twice?

algorithm

numbers

numeric

numerical-methods

divide-and-conquer