具有排序行的矩阵的中值
Median of a Matrix with sorted rows
我无法以最佳方式解决以下问题，也无法在任何地方找到解决此问题的方法。
Given a N × M matrix in which each row is sorted, find the overall median of the matrix. Assume N*M is odd.
For example,
Matrix =
[1, 3, 5]
[2, 6, 9]
[3, 6, 9]
A = [1, 2, 3, 3, 5, 6, 6, 9, 9]
Median is 5. So, we return 5.
Note: No extra memory is allowed.
我们将不胜感激。
考虑以下过程。
如果我们将 N*M 矩阵视为一维数组，则中位数是第 1+N*M/2 个元素。
如果x是矩阵的元素且矩阵元素的个数≤x等于1 + N*M/2.
由于每一行的矩阵元素都是排序的，所以你可以很容易地找到每一行的元素个数less than or equals x。对于在整个矩阵中查找，复杂度为 N*log M 与二进制搜索。
然后先从N*M矩阵中求最小和最大元素。在该范围上应用二分搜索，并对每个 x 应用 运行 上述函数。
如果矩阵 ≤ x 中的元素数是 1 + N*M/2 且 x 包含在该矩阵中，则 x 是中位数。
您可以考虑以下 C++ 代码：
int median(vector<vector<int> > &A) {
int min = A[0][0], max = A[0][0];
int n = A.size(), m = A[0].size();
for (int i = 0; i < n; ++i) {
if (A[i][0] < min) min = A[i][0];
if (A[i][m-1] > max) max = A[i][m-1];
}
int element = (n * m + 1) / 2;
while (min < max) {
int mid = min + (max - min) / 2;
int cnt = 0;
for (int i = 0; i < n; ++i)
cnt += upper_bound(&A[i][0], &A[i][m], mid) - &A[i][0];
if (cnt < element)
min = mid + 1;
else
max = mid;
}
return min;
}
一个简单的 O(1) 内存解决方案是检查每个单独的元素 z 是否是中位数。为此，我们在所有行中找到 z 的位置，只需累加小于 z 的元素数。除了在 O(log M) 时间内在每一行中找到 z 的位置外，这不使用每行已排序的事实。对于每个元素我们需要做N*log M次比较，有N*M个元素，所以是N²M日志 M.
改进和 python 代码：
N×M矩阵的每一行A都排好序，中间有一个元素，也就是它的中位数
至少有 N*(M+1)/2 个元素不大于这些中位数的最大值 hi，并且至少有 N*(M+1)/2 个元素不小于最小 lo:
A 所有元素的中位数必须在 lo 和 hi 之间，包括在内。
一旦已知超过一半的元素低于当前候选元素，则后者已知为高元素。一旦剩余的行太少，低于当前候选者的元素计数达到总数的一半，就知道候选者是低的：在这两种情况下，立即进行下一个候选者。
from bisect import bisect
def median(A):
""" returns the median of all elements in A.
Each row of A needs to be in ascending order. """
# overall median is between min and max row median
lo, hi = minimax(A)
n = len(A)
middle_row = n // 2
columns = len(A[0])
half = (n * columns + 1) // 2
while lo < hi:
mid = lo + (hi - lo) // 2
lower = 0
# first half can't decide median
for a in A[:middle_row]:
lower += bisect(a, mid)
# break as soon as mid is known to be too high or low
for r, a in enumerate(A[middle_row:n-1]):
lower += bisect(a, mid)
if half <= lower:
hi = mid
break
if lower < r*columns:
lo = mid + 1
break
else: # decision in last row
lower += bisect(A[n-1], mid)
if half <= lower:
hi = mid
else:
lo = mid + 1
return lo
def minmax(x, y):
"""return min(x, y), max(x, y)"""
if x < y:
return x, y
return y, x
def minimax(A):
""" return min(A[0..m][n//2]), max(A[0..m][n//2]):
minimum and maximum of medians if A is a
row major matrix with sorted rows."""
n = len(A)
half = n // 2
if n % 2:
lo = hi = A[0][half]
else:
lo, hi = minmax(A[0][half], A[1][half])
for i in range(2-n % 2, len(A[0]), 2):
l, h = minmax(A[i][half], A[i+1][half])
if l < lo:
lo = l
if hi< h:
hi = h
return lo, hi
if __name__ =='__main__':
print(median( [[1, 3, 5], [2, 6, 9], [3, 6, 9]] ))
（我认为 std::upper_bound() 和 bisect.bisect() 是等价的（bisect_right() 是别名）。）
对于第二个候选中位数，处理的最后一行可能低于第一次迭代。在接下来的迭代中，rownumber 永远不应该减少 - 懒得考虑 that in ((rename and) increase middle_row as appropriate).
如果矩阵元素是整数，则可以从矩阵范围开始对中位数进行二分查找，寻找高和低。 O(n log m log(hi-low)).
否则，一种具有 O(n²log²m) 最坏情况时间复杂度的方法是二分查找，O(log m)，依次对每一行，O(n)，最接近整个矩阵中位数的元素从左到右，O(n log m)，更新目前最好的。我们知道总体中位数不超过floor(m * n / 2)个严格小于它的元素，加上小于它的元素个数和它出现的次数可以不少于floor(m * n / 2) + 1个。我们在行上使用标准二分搜索，并且——正如 greybeard 指出的那样——跳过对 'best' 范围之外的元素的测试。测试元素与总体中位数的接近程度涉及计算每行中有多少元素严格小于它以及有多少元素相等，这是在 O(n log m) 时间内通过 n 二进制搜索实现的。由于该行已排序，我们知道相对于整体中位数，较大的元素会更多 "to the right"，而较小的元素会更多 "to the left"。
如果允许重新排列矩阵，O(mn log (mn)) 时间复杂度是可能的，方法是就地对矩阵进行排序（例如使用块排序）并返回中间元素。
有一个随机算法可以在 O(n (log n) (log m)) 时间内解决这个问题。它是 Las Vegas algorithm，这意味着它总是给出正确的结果，但可能需要比预期更长的时间。在这种情况下，花费的时间远远超过预期的概率是极小的。
当 m = 1 时，此问题简化为使用常量 space 在只读数组中查找中位数的问题。该问题没有已知的最佳解决方案：请参阅 "Finding median in read-only memory on integer input, Chan et al."
当 m = 1 时，这个问题的简化有一个奇怪的地方是这个 subcase 也是一个 supercase，在m = 1 的算法可以应用于 m > 1 的情况。这个想法是忘记数组行是排序的并将整个存储区域视为大小为 n * m 的未排序数组。因此，例如，对于 m = 1 情况的简单算法，其中检查每个元素以查看它是否是中位数，需要 O(n2) 时间。当 m > 1 时应用它需要 O(n2m2) 时间。
回到m = 1的情况，在比较模型中（其中数组的项可以是整数，字符串，实数，或任何其他可以与不等运算符“<”进行比较的东西， ">")，最著名的确定性解决方案，它使用 space s（其中 s 是一个常数，即在 O(1 )) 有时间 ϴ(2ss!n1 + 1/s), 它比 Whosebug 上讨论的通常算法更复杂（虽然不在 https://cstheory.stackexchange.com or https://cs.stackexchange.com). It uses a chained sequence of algorithms As, As-1, ..., A1, where As+1 calls As. You can read it in "Selection from read-only memory and sorting with minimum data movement", by Munro and Raman.
有一个简单的随机算法，运行时间更短，概率更高。对于任何常量 c，该算法在时间 O(n log n) 中 运行s，概率为 1 - O(n-c)。当数组是大小为 n*m 的矩阵时 O(n m log (n m)).
这个算法很像quickselect，没有在分区时重新排列元素。
import random
def index_range(needle, haystack):
"""The index range' of a value over an array is a pair
consisting of the number of elements in the array less
than that value and the number of elements in the array
less than or equal to the value.
"""
less = same = 0
for x in haystack:
if x < needle: less += 1
elif x == needle: same += 1
return less, less + same
def median(xs):
"""Finds the median of xs using O(1) extra space. Does not
alter xs.
"""
if not xs: return None
# First, find the minimum and maximum of the array and
# their index ranges:
lo, hi = min(xs), max(xs)
lo_begin, lo_end = index_range(lo, xs)
hi_begin, hi_end = index_range(hi, xs)
# Gradually we will move the lo and hi index ranges closer
# to the median.
mid_idx = len(xs)//2
while True:
print "range size", hi_begin - lo_end
if lo_begin <= mid_idx < lo_end:
return lo
if hi_begin <= mid_idx < hi_end:
return hi
assert hi_begin - lo_end > 0
# Loop over the array, inspecting each item between lo
# and hi. This loops sole purpose is to reservoir sample
# from that set. This makes res a randomly selected
# element from among those strictly between lo and hi in
# xs:
res_size = 0
res = None
for x in xs:
if lo < x < hi:
res_size += 1
if 1 == random.randint(1, res_size):
res = x
assert res is not None
assert hi_begin - lo_end == res_size
# Now find which size of the median res is on and
# continue the search on the smaller region:
res_begin, res_end = index_range(res, xs)
if res_end > mid_idx:
hi, hi_begin, hi_end = res, res_begin, res_end
else:
lo, lo_begin, lo_end = res, res_begin, res_end
它的工作原理是维持中位数值的上限和下限。然后它遍历数组并随机选择边界之间的值。该值替换了其中一个界限，并且该过程再次开始。
边界伴随着它们的索引范围，这是对数组排序后边界将出现在哪些索引处的度量。一旦边界之一出现在索引 ⌊n/2⌋ 处，它就是中位数，算法终止。
当在边界之间的间隙中随机选择一个元素时，这会减少 50% 的预期间隙。当间隙为 0 时，该算法（最迟）终止。我们可以将其建模为来自 (0,1) 的一系列随机独立均匀分布变量 Xi 使得 Yk = X1 * X2 * ... * Xk 其中 Xi 是第 i 轮后剩余差距的比率。例如，如果在第 10 轮之后 lo 和 hi 的索引范围之间的差距为 120，并且在第 11 轮之后差距为 90，则 X11 = 0.75。当 Yk < 1/n 时算法终止，因为此时间隙小于 1.
选择一个常量正整数k。让我们使用 Chernoff 界限来限制 Yk log2n >= 1/n 的概率。我们有 Yk log2n = X1 * X2 * ... Xk log2n, 所以 ln Yk log2n = ln X1 + ln X2 + ... + ln X k log2n。切尔诺夫边界然后给出 Pr(ln X1 + ln X2 + ... + ln Xk log2n >= ln (1/n)) <= mint > 0 e-t ln ( 1/n) (E[et ln X1] * E[et ln X 2] * ... * E[et ln Xk log2 n])。经过一些简化，右边是 mint > 0 nt (E[X1t] * E[X2t] * ... * E[Xk log2 nt])。由于这是一个最小值，我们正在寻找一个上限，我们可以通过特化到 t = 1 来削弱它。然后它简化为 n1-k，因为 E[Xi] = 1/2.
如果我们选择，例如，k = 6，那么这将有 6 log2n 轮或更多轮的概率限制为 n-5 。因此，概率为 1 - O(n-5) 时，算法执行 6 log2n - 1 轮或更少。这就是我上面"with high probability"的意思。
由于每一轮检查数组的每个成员的次数都是固定的，所以每一轮都需要线性时间，总 运行宁时间很可能是 O(n log n)。当数组不仅仅是一个数组，而是一个大小为 n * m 的矩阵时，计算结果为 O(n m log (n m)).
但是，通过利用行的排序，我们可以做得更好。当我们在单个未排序的数组中工作时，找到我上面提到的间隙中的元素需要检查数组的每个元素。在具有已排序行的矩阵中，间隙中的元素位于每行的连续段中。使用二进制搜索可以在 O(log m) 时间内识别每个段，因此它们都可以在 O(n log m) 时间内定位。水库采样现在每次循环迭代需要 O(n log m) 时间。
循环中完成的另一个主要工作是从随机选择的间隙中识别元素的索引范围。同样，因为每一行都已排序，所以可以在 O(log m) 时间内确定一行中随机选择的元素的索引范围。每行的索引范围之和构成了整个数组的索引范围，因此每次循环迭代的这一部分也只需要 O(n log m) 时间。
通过与上述切尔诺夫边界相同的论证，对于任何常数 k，有 O(log n) 次迭代概率至少为 1-O(n-k) .因此整个算法以高概率花费 O(n (log n) (log m)) 时间。
import bisect
import random
def matrix_index_range(needle, haystack):
"""matrix_index_range calculates the index range of needle
in a haystack that is a matrix (stored in row-major order)
in which each row is sorted"""
n, m = len(haystack), len(haystack[0])
begin = end = 0;
for x in haystack:
begin += bisect.bisect_left(x, needle)
end += bisect.bisect_right(x, needle)
return begin, end
def matrix_median(xs):
print "Starting"
if not xs or not xs[0]: return None
n, m = len(xs), len(xs[0])
lo, hi = xs[0][0], xs[0][m-1]
for x in xs:
lo, hi = min(lo, x[0]), max(hi, x[m-1])
lo_begin, lo_end = matrix_index_range(lo, xs)
hi_begin, hi_end = matrix_index_range(hi, xs)
mid_idx = (n * m) // 2
while True:
print "range size", hi_begin - lo_end
if lo_begin <= mid_idx < lo_end:
return lo
if hi_begin <= mid_idx < hi_end:
return hi
assert hi_begin - lo_end > 0
mid = None
midth = random.randint(0, hi_begin - lo_end - 1)
for x in xs:
gap_begin = bisect.bisect_right(x, lo)
gap_end = bisect.bisect_left(x, hi)
gap_size = gap_end - gap_begin
if midth < gap_size:
mid = x[gap_begin + midth]
break
midth -= gap_size
assert mid is not None
mid_begin, mid_end = matrix_index_range(mid, xs)
assert lo_end <= mid_begin and mid_end <= hi_begin
if mid_end > mid_idx:
hi, hi_begin, hi_end = mid, mid_begin, mid_end
else:
lo, lo_begin, lo_end = mid, mid_begin, mid_end
当 m 为非常数时，此解决方案比第一个解决方案快得多。
我已经编写了 O(n2 log2 m) 时间解决方案，但他们要求我不要将代码添加到他们的答案中，所以这里是一个单独的答案：
import bisect
def MedianDistance(key, matrix):
lo = hi = 0
for row in matrix:
lo += bisect.bisect_left(row, key)
hi += bisect.bisect_right(row, key)
mid = len(matrix) * len(matrix[0]) // 2;
if hi - 1 < mid: return hi - 1 - mid
if lo > mid: return lo - mid
return 0
def ZeroInSorted(row, measure):
lo, hi = -1, len(row)
while hi - lo > 1:
mid = (lo + hi) // 2
ans = measure(row[mid])
if ans < 0: lo = mid
elif ans == 0: return mid
else: hi = mid
def MatrixMedian(matrix):
measure = lambda x: MedianDistance(x, matrix)
for idx, row in enumerate(matrix):
if not idx & idx-1: print(idx)
ans = ZeroInSorted(row, measure)
if ans is not None: return row[ans]
使用拉斯维加斯算法：
from random import randint
def findMedian(matrix):
#getting the length of columns and rows
N = len(matrix)
M = len(matrix[0])
while True:
counter = 0
#select a row randomly
u = randint(0,len(matrix)-1)
#select a column randomly
v = randint(0,len(matrix[0])-1)
#random index
x = matrix[u][v]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] < x:
counter+=1
#finding median
if counter == (N*M-1)//2:
return (x)
arr = [[1,3,5],
[2,6,9],
[3,6,9]]
findMedian(arr)
据我所知，人们对@sunkuet02 算法有很多疑问。我将尝试回答这个问题。这可能对其他人有帮助。
向@user248884 提问。
1）为什么是max=mid而不是max=mid-1？
if (cnt < element)
min = mid + 1;
else
max = mid;
解决方案可以是中间元素。假设我们有 r=1 c=4 和 A[][4]={{1,2,9,10}}；
此处，最小值 = 1，最大值 = 10。因此 mid=5 这就是答案。
这意味着你不能离开中间元素。
2) 为什么我们 return 分钟？
其实没关系。您也可以 return max，因为两者都会给出相同的答案。
while (min < max) { ...}
While 循环会在 min == max 时中断。所以，一个可以 return min 或 max 都没有关系。想一想。
@Seaky Lone 提问
3。 upper_bound() 是什么？
这个函数需要 3 个参数数组开始（更准确地说是迭代器开始）、直到您要检查的最后一个索引（不包括最后一个元素）和一个 X。它将 return 大于 X 的第一个元素索引。使用这个函数可以得到小于X的元素个数。
@dk123 提出的问题
4.How 我们确定 mid 实际上是矩阵中的一个数字吗？
在此算法中，我们不检查数组中是否存在中位数。
为此，在获得可能的中位数后，检查矩阵是否存在。如果不是，则找到最接近中位数的最小元素
此题与在按行和按列排序的矩阵中查找第 k 个最小元素非常相似。
所以这个问题可以在排序矩阵中使用二进制搜索和优化计数来解决。二进制搜索需要 O(log(n)) 时间，对于每个搜索值，平均需要 n 次迭代才能找到小于搜索数字的数字。二分查找的搜索space限制在矩阵中的最小值mat[0][0]和最大值mat[n-1][n-1].
对于从二进制搜索中选择的每个数字，我们需要计算小于或等于该特定数字的数字。因此可以找到第k^个最小的数字或中位数。
为了更好地理解您可以参考这个视频：
我无法以最佳方式解决以下问题，也无法在任何地方找到解决此问题的方法。
Given a N × M matrix in which each row is sorted, find the overall median of the matrix. Assume N*M is odd.
For example,
Matrix =
[1, 3, 5]
[2, 6, 9]
[3, 6, 9]A = [1, 2, 3, 3, 5, 6, 6, 9, 9]
Median is 5. So, we return 5.
Note: No extra memory is allowed.
我们将不胜感激。
考虑以下过程。
如果我们将 N*M 矩阵视为一维数组，则中位数是第
1+N*M/2个元素。如果x是矩阵的元素且矩阵元素的个数≤x等于
1 + N*M/2. 则认为x是中位数
由于每一行的矩阵元素都是排序的，所以你可以很容易地找到每一行的元素个数
less than or equals x。对于在整个矩阵中查找，复杂度为N*log M与二进制搜索。然后先从N*M矩阵中求最小和最大元素。在该范围上应用二分搜索，并对每个 x 应用 运行 上述函数。
如果矩阵
≤ x中的元素数是1 + N*M/2且 x 包含在该矩阵中，则x是中位数。
您可以考虑以下 C++ 代码：
int median(vector<vector<int> > &A) {
int min = A[0][0], max = A[0][0];
int n = A.size(), m = A[0].size();
for (int i = 0; i < n; ++i) {
if (A[i][0] < min) min = A[i][0];
if (A[i][m-1] > max) max = A[i][m-1];
}
int element = (n * m + 1) / 2;
while (min < max) {
int mid = min + (max - min) / 2;
int cnt = 0;
for (int i = 0; i < n; ++i)
cnt += upper_bound(&A[i][0], &A[i][m], mid) - &A[i][0];
if (cnt < element)
min = mid + 1;
else
max = mid;
}
return min;
}
一个简单的 O(1) 内存解决方案是检查每个单独的元素 z 是否是中位数。为此，我们在所有行中找到 z 的位置，只需累加小于 z 的元素数。除了在 O(log M) 时间内在每一行中找到 z 的位置外，这不使用每行已排序的事实。对于每个元素我们需要做N*log M次比较，有N*M个元素，所以是N²M日志 M.
N×M矩阵的每一行A都排好序，中间有一个元素，也就是它的中位数
至少有 N*(M+1)/2 个元素不大于这些中位数的最大值 hi，并且至少有 N*(M+1)/2 个元素不小于最小 lo:
A 所有元素的中位数必须在 lo 和 hi 之间，包括在内。
一旦已知超过一半的元素低于当前候选元素，则后者已知为高元素。一旦剩余的行太少，低于当前候选者的元素计数达到总数的一半，就知道候选者是低的：在这两种情况下，立即进行下一个候选者。
from bisect import bisect
def median(A):
""" returns the median of all elements in A.
Each row of A needs to be in ascending order. """
# overall median is between min and max row median
lo, hi = minimax(A)
n = len(A)
middle_row = n // 2
columns = len(A[0])
half = (n * columns + 1) // 2
while lo < hi:
mid = lo + (hi - lo) // 2
lower = 0
# first half can't decide median
for a in A[:middle_row]:
lower += bisect(a, mid)
# break as soon as mid is known to be too high or low
for r, a in enumerate(A[middle_row:n-1]):
lower += bisect(a, mid)
if half <= lower:
hi = mid
break
if lower < r*columns:
lo = mid + 1
break
else: # decision in last row
lower += bisect(A[n-1], mid)
if half <= lower:
hi = mid
else:
lo = mid + 1
return lo
def minmax(x, y):
"""return min(x, y), max(x, y)"""
if x < y:
return x, y
return y, x
def minimax(A):
""" return min(A[0..m][n//2]), max(A[0..m][n//2]):
minimum and maximum of medians if A is a
row major matrix with sorted rows."""
n = len(A)
half = n // 2
if n % 2:
lo = hi = A[0][half]
else:
lo, hi = minmax(A[0][half], A[1][half])
for i in range(2-n % 2, len(A[0]), 2):
l, h = minmax(A[i][half], A[i+1][half])
if l < lo:
lo = l
if hi< h:
hi = h
return lo, hi
if __name__ =='__main__':
print(median( [[1, 3, 5], [2, 6, 9], [3, 6, 9]] ))
（我认为 std::upper_bound() 和 bisect.bisect() 是等价的（bisect_right() 是别名）。）
对于第二个候选中位数，处理的最后一行可能低于第一次迭代。在接下来的迭代中，rownumber 永远不应该减少 - 懒得考虑 that in ((rename and) increase middle_row as appropriate).
如果矩阵元素是整数，则可以从矩阵范围开始对中位数进行二分查找，寻找高和低。 O(n log m log(hi-low)).
否则，一种具有 O(n²log²m) 最坏情况时间复杂度的方法是二分查找，O(log m)，依次对每一行，O(n)，最接近整个矩阵中位数的元素从左到右，O(n log m)，更新目前最好的。我们知道总体中位数不超过floor(m * n / 2)个严格小于它的元素，加上小于它的元素个数和它出现的次数可以不少于floor(m * n / 2) + 1个。我们在行上使用标准二分搜索，并且——正如 greybeard 指出的那样——跳过对 'best' 范围之外的元素的测试。测试元素与总体中位数的接近程度涉及计算每行中有多少元素严格小于它以及有多少元素相等，这是在 O(n log m) 时间内通过 n 二进制搜索实现的。由于该行已排序，我们知道相对于整体中位数，较大的元素会更多 "to the right"，而较小的元素会更多 "to the left"。
如果允许重新排列矩阵，O(mn log (mn)) 时间复杂度是可能的，方法是就地对矩阵进行排序（例如使用块排序）并返回中间元素。
有一个随机算法可以在 O(n (log n) (log m)) 时间内解决这个问题。它是 Las Vegas algorithm，这意味着它总是给出正确的结果，但可能需要比预期更长的时间。在这种情况下，花费的时间远远超过预期的概率是极小的。
当 m = 1 时，此问题简化为使用常量 space 在只读数组中查找中位数的问题。该问题没有已知的最佳解决方案：请参阅 "Finding median in read-only memory on integer input, Chan et al."
当 m = 1 时，这个问题的简化有一个奇怪的地方是这个 subcase 也是一个 supercase，在m = 1 的算法可以应用于 m > 1 的情况。这个想法是忘记数组行是排序的并将整个存储区域视为大小为 n * m 的未排序数组。因此，例如，对于 m = 1 情况的简单算法，其中检查每个元素以查看它是否是中位数，需要 O(n2) 时间。当 m > 1 时应用它需要 O(n2m2) 时间。
回到m = 1的情况，在比较模型中（其中数组的项可以是整数，字符串，实数，或任何其他可以与不等运算符“<”进行比较的东西， ">")，最著名的确定性解决方案，它使用 space s（其中 s 是一个常数，即在 O(1 )) 有时间 ϴ(2ss!n1 + 1/s), 它比 Whosebug 上讨论的通常算法更复杂（虽然不在 https://cstheory.stackexchange.com or https://cs.stackexchange.com). It uses a chained sequence of algorithms As, As-1, ..., A1, where As+1 calls As. You can read it in "Selection from read-only memory and sorting with minimum data movement", by Munro and Raman.
有一个简单的随机算法，运行时间更短，概率更高。对于任何常量 c，该算法在时间 O(n log n) 中 运行s，概率为 1 - O(n-c)。当数组是大小为 n*m 的矩阵时 O(n m log (n m)).
这个算法很像quickselect，没有在分区时重新排列元素。
import random
def index_range(needle, haystack):
"""The index range' of a value over an array is a pair
consisting of the number of elements in the array less
than that value and the number of elements in the array
less than or equal to the value.
"""
less = same = 0
for x in haystack:
if x < needle: less += 1
elif x == needle: same += 1
return less, less + same
def median(xs):
"""Finds the median of xs using O(1) extra space. Does not
alter xs.
"""
if not xs: return None
# First, find the minimum and maximum of the array and
# their index ranges:
lo, hi = min(xs), max(xs)
lo_begin, lo_end = index_range(lo, xs)
hi_begin, hi_end = index_range(hi, xs)
# Gradually we will move the lo and hi index ranges closer
# to the median.
mid_idx = len(xs)//2
while True:
print "range size", hi_begin - lo_end
if lo_begin <= mid_idx < lo_end:
return lo
if hi_begin <= mid_idx < hi_end:
return hi
assert hi_begin - lo_end > 0
# Loop over the array, inspecting each item between lo
# and hi. This loops sole purpose is to reservoir sample
# from that set. This makes res a randomly selected
# element from among those strictly between lo and hi in
# xs:
res_size = 0
res = None
for x in xs:
if lo < x < hi:
res_size += 1
if 1 == random.randint(1, res_size):
res = x
assert res is not None
assert hi_begin - lo_end == res_size
# Now find which size of the median res is on and
# continue the search on the smaller region:
res_begin, res_end = index_range(res, xs)
if res_end > mid_idx:
hi, hi_begin, hi_end = res, res_begin, res_end
else:
lo, lo_begin, lo_end = res, res_begin, res_end
它的工作原理是维持中位数值的上限和下限。然后它遍历数组并随机选择边界之间的值。该值替换了其中一个界限，并且该过程再次开始。
边界伴随着它们的索引范围，这是对数组排序后边界将出现在哪些索引处的度量。一旦边界之一出现在索引 ⌊n/2⌋ 处，它就是中位数，算法终止。
当在边界之间的间隙中随机选择一个元素时，这会减少 50% 的预期间隙。当间隙为 0 时，该算法（最迟）终止。我们可以将其建模为来自 (0,1) 的一系列随机独立均匀分布变量 Xi 使得 Yk = X1 * X2 * ... * Xk 其中 Xi 是第 i 轮后剩余差距的比率。例如，如果在第 10 轮之后 lo 和 hi 的索引范围之间的差距为 120，并且在第 11 轮之后差距为 90，则 X11 = 0.75。当 Yk < 1/n 时算法终止，因为此时间隙小于 1.
选择一个常量正整数k。让我们使用 Chernoff 界限来限制 Yk log2n >= 1/n 的概率。我们有 Yk log2n = X1 * X2 * ... Xk log2n, 所以 ln Yk log2n = ln X1 + ln X2 + ... + ln X k log2n。切尔诺夫边界然后给出 Pr(ln X1 + ln X2 + ... + ln Xk log2n >= ln (1/n)) <= mint > 0 e-t ln ( 1/n) (E[et ln X1] * E[et ln X 2] * ... * E[et ln Xk log2 n])。经过一些简化，右边是 mint > 0 nt (E[X1t] * E[X2t] * ... * E[Xk log2 nt])。由于这是一个最小值，我们正在寻找一个上限，我们可以通过特化到 t = 1 来削弱它。然后它简化为 n1-k，因为 E[Xi] = 1/2.
如果我们选择，例如，k = 6，那么这将有 6 log2n 轮或更多轮的概率限制为 n-5 。因此，概率为 1 - O(n-5) 时，算法执行 6 log2n - 1 轮或更少。这就是我上面"with high probability"的意思。
由于每一轮检查数组的每个成员的次数都是固定的，所以每一轮都需要线性时间，总 运行宁时间很可能是 O(n log n)。当数组不仅仅是一个数组，而是一个大小为 n * m 的矩阵时，计算结果为 O(n m log (n m)).
但是，通过利用行的排序，我们可以做得更好。当我们在单个未排序的数组中工作时，找到我上面提到的间隙中的元素需要检查数组的每个元素。在具有已排序行的矩阵中，间隙中的元素位于每行的连续段中。使用二进制搜索可以在 O(log m) 时间内识别每个段，因此它们都可以在 O(n log m) 时间内定位。水库采样现在每次循环迭代需要 O(n log m) 时间。
循环中完成的另一个主要工作是从随机选择的间隙中识别元素的索引范围。同样，因为每一行都已排序，所以可以在 O(log m) 时间内确定一行中随机选择的元素的索引范围。每行的索引范围之和构成了整个数组的索引范围，因此每次循环迭代的这一部分也只需要 O(n log m) 时间。
通过与上述切尔诺夫边界相同的论证，对于任何常数 k，有 O(log n) 次迭代概率至少为 1-O(n-k) .因此整个算法以高概率花费 O(n (log n) (log m)) 时间。
import bisect
import random
def matrix_index_range(needle, haystack):
"""matrix_index_range calculates the index range of needle
in a haystack that is a matrix (stored in row-major order)
in which each row is sorted"""
n, m = len(haystack), len(haystack[0])
begin = end = 0;
for x in haystack:
begin += bisect.bisect_left(x, needle)
end += bisect.bisect_right(x, needle)
return begin, end
def matrix_median(xs):
print "Starting"
if not xs or not xs[0]: return None
n, m = len(xs), len(xs[0])
lo, hi = xs[0][0], xs[0][m-1]
for x in xs:
lo, hi = min(lo, x[0]), max(hi, x[m-1])
lo_begin, lo_end = matrix_index_range(lo, xs)
hi_begin, hi_end = matrix_index_range(hi, xs)
mid_idx = (n * m) // 2
while True:
print "range size", hi_begin - lo_end
if lo_begin <= mid_idx < lo_end:
return lo
if hi_begin <= mid_idx < hi_end:
return hi
assert hi_begin - lo_end > 0
mid = None
midth = random.randint(0, hi_begin - lo_end - 1)
for x in xs:
gap_begin = bisect.bisect_right(x, lo)
gap_end = bisect.bisect_left(x, hi)
gap_size = gap_end - gap_begin
if midth < gap_size:
mid = x[gap_begin + midth]
break
midth -= gap_size
assert mid is not None
mid_begin, mid_end = matrix_index_range(mid, xs)
assert lo_end <= mid_begin and mid_end <= hi_begin
if mid_end > mid_idx:
hi, hi_begin, hi_end = mid, mid_begin, mid_end
else:
lo, lo_begin, lo_end = mid, mid_begin, mid_end
当 m 为非常数时，此解决方案比第一个解决方案快得多。
我已经编写了 O(n2 log2 m) 时间解决方案，但他们要求我不要将代码添加到他们的答案中，所以这里是一个单独的答案：
import bisect
def MedianDistance(key, matrix):
lo = hi = 0
for row in matrix:
lo += bisect.bisect_left(row, key)
hi += bisect.bisect_right(row, key)
mid = len(matrix) * len(matrix[0]) // 2;
if hi - 1 < mid: return hi - 1 - mid
if lo > mid: return lo - mid
return 0
def ZeroInSorted(row, measure):
lo, hi = -1, len(row)
while hi - lo > 1:
mid = (lo + hi) // 2
ans = measure(row[mid])
if ans < 0: lo = mid
elif ans == 0: return mid
else: hi = mid
def MatrixMedian(matrix):
measure = lambda x: MedianDistance(x, matrix)
for idx, row in enumerate(matrix):
if not idx & idx-1: print(idx)
ans = ZeroInSorted(row, measure)
if ans is not None: return row[ans]
使用拉斯维加斯算法：
from random import randint
def findMedian(matrix):
#getting the length of columns and rows
N = len(matrix)
M = len(matrix[0])
while True:
counter = 0
#select a row randomly
u = randint(0,len(matrix)-1)
#select a column randomly
v = randint(0,len(matrix[0])-1)
#random index
x = matrix[u][v]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] < x:
counter+=1
#finding median
if counter == (N*M-1)//2:
return (x)
arr = [[1,3,5],
[2,6,9],
[3,6,9]]
findMedian(arr)
据我所知，人们对@sunkuet02 算法有很多疑问。我将尝试回答这个问题。这可能对其他人有帮助。
向@user248884 提问。
1）为什么是max=mid而不是max=mid-1？
if (cnt < element)
min = mid + 1;
else
max = mid;
解决方案可以是中间元素。假设我们有 r=1 c=4 和 A[][4]={{1,2,9,10}}； 此处，最小值 = 1，最大值 = 10。因此 mid=5 这就是答案。 这意味着你不能离开中间元素。
2) 为什么我们 return 分钟？ 其实没关系。您也可以 return max，因为两者都会给出相同的答案。
while (min < max) { ...}
While 循环会在 min == max 时中断。所以，一个可以 return min 或 max 都没有关系。想一想。
@Seaky Lone 提问
3。 upper_bound() 是什么？ 这个函数需要 3 个参数数组开始（更准确地说是迭代器开始）、直到您要检查的最后一个索引（不包括最后一个元素）和一个 X。它将 return 大于 X 的第一个元素索引。使用这个函数可以得到小于X的元素个数。
@dk123 提出的问题
4.How 我们确定 mid 实际上是矩阵中的一个数字吗？
在此算法中，我们不检查数组中是否存在中位数。 为此，在获得可能的中位数后，检查矩阵是否存在。如果不是，则找到最接近中位数的最小元素
此题与在按行和按列排序的矩阵中查找第 k 个最小元素非常相似。
所以这个问题可以在排序矩阵中使用二进制搜索和优化计数来解决。二进制搜索需要 O(log(n)) 时间，对于每个搜索值，平均需要 n 次迭代才能找到小于搜索数字的数字。二分查找的搜索space限制在矩阵中的最小值mat[0][0]和最大值mat[n-1][n-1].
对于从二进制搜索中选择的每个数字，我们需要计算小于或等于该特定数字的数字。因此可以找到第k^个最小的数字或中位数。
为了更好地理解您可以参考这个视频：