python - 在整数的大整数文件中查找中位数

Question

我在采访中被问到以下问题。我没有得到它，但试图在家里解决它。我相信我们必须使用 Median of Median 算法...

Q: Finding Median in Large Integer File of Integers

Find the median from a large file of integers. You can not access the numbers by index, can only access it sequentially. And the numbers cannot fit in memory.

我在网上找到了一个解决方案(用 Python 重写)，但有几件事我不明白。我有点了解算法，但不是 100% 确定。

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

Answer 1

这只是 binary search按中值

与示例代码比较

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 的情况类似但相反案例