寻找大整数文件中的中位数

Question

我在面试中被问到以下问题。我当时不理解，但现在正在尝试在家里解决它。我相信我们必须使用“中位数算法”...

Q: 在一个大整数文件中查找中位数

从一个大的整数文件中查找中位数。您不能通过索引访问数字，只能按顺序访问。而且这些数字无法放入内存。

我在网上找到了一个解决方案（用Python重写），但有几个问题我不太明白...我有点理解算法，但不确定是否完全正确。

a) 为什么要检查left >= right？

b) 当count < k时，我们调用self.findMedianInLargeFile(numbers,k,max(result+1,guess),right)。为什么将max(result+1, guess)称为left？

c) 当count > k时，为什么要使用result作为right？

class Solution:

def findMedianInLargeFile(self, numbers,k,left,right):

    if left >= right:
        return left

    result = left
    guess = (left + right ) // 2
    count = 0

    # count the number that is less than guess

    for i in numbers:
        if i <= guess:
            count+=1
            result = max(result,i)

    if count == k:
        return result
    elif count < k: # if the number of items < guess is < K
        return self.findMedianInLargeFile(numbers,k,max(result+1,guess),right)
    else: 
        return self.findMedianInLargeFile(numbers,k,left,result)



def findMedian(self, numbers):
    length = len(numbers)

    if length % 2 == 1: # odd
        return self.findMedianInLargeFile(numbers,length//2 + 1,-999999999,999999999)
    else:
        return (self.findMedianInLargeFile(numbers,length//2,-999999999,999999999) + self.findMedianInLargeFile(numbers,length//2 +1 ,-999999999,999999999)) / 2

- user82383

Answer 1

这只是通过中位数值进行的二分查找

与示例代码进行比较

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

• if left >= right: 如果边界相遇，就停止迭代

• 当 count < k 时，我们调用 self.findMedianInLargeFile(numbers,k,max(result+1,guess),right) ，因为我们的猜测值太小了，中位数比猜测值大。

• 对于else情况，类似但是相反

- MBo

---

啊，没错。谢谢 @mbo。为什么要使用 "result = max(result,i)"？另外，在 "return self.findMedianInLargeFile(numbers,k,left,result)" 中，为什么我们没有减去1呢？ - user82383

我们不减去1，因为右边界是被排除的（与Python相似）。最大条件 - 用于处理数字小于左边界的情况。 - MBo

Answer 2

您可以在外部存储器上执行-- O(nlogn) --的归并排序，因为它被实现为按顺序处理数据。

一个有趣的解决方案是通过顺序统计树实现，其实现可在此处获得：Median of large amount of numbers for each sets of given size 但是，如果您有任何问题--请让我知道！

- Drimik Roy