我在面试中被问到以下问题。我当时不理解,但现在正在尝试在家里解决它。我相信我们必须使用“中位数算法”...
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