假設我們有兩個陣列：
陣列1 = [2,3,6,7,9]
陣列2 = [1,4,8,10]
我了解如何在log(min(m,n))中找到兩個排序陣列的第 k 個元素，其中m是 array1 的長度，n是 array2 的長度，如下所示：
def kthelement(arr1, arr2, m, n, k):
if m > n:
kthelement(arr2, arr1, n, m, k)
low = max(0, k - m)
high = min(k, n)
while low <= high:
cut1 = (low high) >> 1
cut2 = k - cut1
l1 = MIN_VALUE if cut1 == 0 else arr1[cut1 - 1]
l2 = MIN_VALUE if cut2 == 0 else arr2[cut2 - 1]
r1 = MAX_VALUE if cut1 == n else arr1[cut1]
r2 = MAX_VALUE if cut2 == m else arr2[cut2]
if l1 <= r2 and l2 <= r1:
print(cut1, cut2)
return max(l1, l2)
elif l1 > r2:
high = cut1 - 1
else:
low = cut1 1
但我不知道如何將其擴展到多個排序陣列的情況。例如，給定 3 個陣列，我想找到最終排序陣列的第 k 個元素。
陣列1 = [2,3,6,7,9]
陣列2 = [1,4,8,10]
陣列3 = [2,3,5,7]
是否可以像在兩個陣列的情況下那樣在log(min(m,n))中實作它？
uj5u.com熱心網友回復：
如果 k 很大，我們可以對答案進行二分搜索，這導致了一個具有時間復雜度的解，O(n*logN)其中 N 是每個元素的范圍，并且n是陣列的數量。
我們需要學習的是如何檢查某個整數x是否<=正確。我們可以列舉每個陣列，并對其進行二進制搜索以計算小于或等于 x 的元素數。累積它們，并與 比較k。
from typing import List
import bisect
def query_k_min(vecs: List[List[int]], k: int) -> int:
# we assume each number >=1 and <=10^9
l, r = 0, 10**9
while r - l > 1:
m = (l r)>>1
tot = 0
for vec in vecs:
tot = bisect.bisect_right(vec, m)
if tot >= k: r = m
else: l = m
return r
a = [[2,3,6,7,9],[1,4,8,10],[2,3,5,7]]
for x in range(1,14):
print(query_k_min(a,x))
uj5u.com熱心網友回復：
下面看起來很復雜，但如果M是 的對數之和len(list) 2，那么平均情況是O(M)，最壞情況是O(M^2)。（ 2 的原因是即使陣列沒有元素，我們也需要做一些作業，我們通過使 log 至少為 2 來做到這一點。）最壞的情況不太可能發生。
性能獨立于k.
這個想法與Quickselect相同。我們正在挑選支點，并圍繞支點拆分資料。但是我們不查看每個元素，我們只找出仍在考慮中的每個陣列的哪個塊在樞軸之前/之后/著陸。平均情況是因為每次我們查看一個陣列時，我們都會以正概率擺脫剩下的一半。最壞的情況是，因為每次我們查看從中獲得軸心的陣列時，我們都會洗掉該陣列的一半，但可能必須對每個其他陣列進行二分搜索才能確定我們沒有洗掉其他任何內容。
from collections import deque
def kth_of_sorted (k, arrays):
# Initialize some global variables.
known_low = 0
known_high = 0
total_size = 0
# in_flight will be a double-ended queue of
# (array, iteration, i, j, min_i, min_j)
# Where:
# array is an input array
# iteration is which median it was compared to
# low is the lower bound on where kth might be
# high is the upper bound on where kth might be
in_flight = deque()
for a in arrays:
if 0 < len(a):
total_size = len(a)
in_flight.append((a, 0, len(a)-1))
# Sanity check.
if k < 1 or total_size < k:
return None
while 0 < len(in_flight):
start_a, start_low, start_high = in_flight.popleft()
start_mid = (start_low start_high) // 2
pivot = start_a[start_mid]
# If pivot is placed, how many are known?
maybe_low = start_mid - start_low
maybe_high = start_high - start_mid
# This will be arrays taken from in_flight with:
#
# (array, low, high, orig_low, orig_high)
#
# We are binary searching in these to figure out where the pivot
# is going to go. Then we copy back to in_flight.
to_process = deque()
# This will be arrays taken from in_flight with:
#
# (array, orig_low, mid, orig_high)
#
# where at mid we match the pivot.
is_match = deque()
# And we know an array with a pivot!
is_match.append((start_a, start_low, start_mid, start_high))
# This will be arrays taken from in_flight which we know do not have the pivot:
#
# (array, low, high, orig_low, orig_high)
#
no_pivot = deque()
while 0 < len(in_flight):
a, low, high = in_flight.popleft()
mid = (low high) // 2
if a[mid] < pivot:
# all of low, low 1, ..., mid are below the pivot
maybe_low = mid 1 - low
if mid < high:
to_process.append((a, mid 1, high, low, high))
else:
no_pivot.append((a, mid 1, high, low, high))
elif pivot < a[mid]:
# all of mid, mid 1, ..., high are above the pivot.
maybe_high = high 1 - mid
if low < mid:
to_process.append((a, low, mid-1, low, high))
else:
no_pivot.append((a, low, mid-1, low, high))
else:
# mid is at pivot
maybe_low = mid - low
maybe_high = high - mid
is_match.append((a, low, mid, high))
# We do not yet know where the pivot_pos is.
pivot_pos = None
if k <= known_low maybe_low:
pivot_pos = 'right'
elif total_size - known_high - maybe_high < k:
pivot_pos = 'left'
elif k <= known_low maybe_low len(is_match) and total_size < k known_high maybe_high len(is_match):
return pivot # WE FOUND IT!
while pivot_pos is None:
# This is very similar to how we processed in_flight.
a, low, high, orig_low, orig_high = to_process.popleft()
mid = (low high) // 2
if a[mid] < pivot:
# all of low, low 1, ..., mid are below the pivot
maybe_low = mid 1 - low
if mid < high:
to_process.append((a, mid 1, high, orig_low, orig_high))
else:
no_pivot.append((a, mid 1, high, orig_low, orig_high))
elif pivot < a[mid]:
# all of mid, mid 1, ..., high are above the pivot.
maybe_high = high 1 - mid
if low < mid:
to_process.append((a, low, mid-1, orig_low, orig_high))
else:
no_pivot.append((a, low, mid-1, orig_low, orig_high))
else:
# mid is at pivot
maybe_low = mid - low
maybe_high = high - mid
is_match.append((a, orig_low, mid, orig_high))
if k <= known_low maybe_low:
pivot_pos = 'right'
elif total_size - known_high - maybe_high < k:
pivot_pos = 'left'
a, low, high = in_flight.popleft()
mid = (low high) // 2
if a[mid] < pivot:
# all of low, low 1, ..., mid are below the pivot
maybe_low = mid 1 - low
if mid < high:
to_process.append((a, mid 1, high, low, high))
else:
no_pivot.append((a, mid 1, high, low, high))
elif pivot < a[mid]:
# all of mid, mid 1, ..., high are above the pivot.
maybe_high = high 1 - mid
if low < mid:
to_process.append((a, low, mid-1, low, high))
else:
no_pivot.append((a, low, mid-1, low, high))
else:
# mid is at pivot
maybe_low = mid - low
maybe_high = high - mid
is_match.append((a, low, mid, high))
# We do not yet know where the pivot_pos is.
pivot_pos = None
if k <= known_low maybe_low:
pivot_pos = 'right'
elif total_size - known_high - maybe_high < k:
pivot_pos = 'left'
elif k <= known_low maybe_low len(is_match) and total_size < k known_high maybe_high len(is_match):
return pivot # WE FOUND IT!
while pivot_pos is None:
# This is very similar to how we processed in_flight.
a, low, high, orig_low, orig_high = to_process.popleft()
mid = (low high) // 2
if a[mid] < pivot:
# all of low, low 1, ..., mid are below the pivot
maybe_low = mid 1 - low
if mid < high:
to_process.append((a, mid 1, high, orig_low, orig_high))
else:
no_pivot.append((a, mid 1, high, orig_low, orig_high))
elif pivot < a[mid]:
# all of mid, mid 1, ..., high are above the pivot.
maybe_high = high 1 - mid
if low < mid:
to_process.append((a, low, mid-1, orig_low, orig_high))
else:
no_pivot.append((a, low, mid-1, orig_low, orig_high))
else:
# mid is at pivot
maybe_low = mid - low
maybe_high = high - mid
is_match.append((a, orig_low, mid, orig_high))
if k <= known_low maybe_low:
pivot_pos = 'right'
elif total_size - known_high - maybe_high < k:
pivot_pos = 'left'
elif k <= known_low maybe_low len(is_match) and total_size < k known_high maybe_high len(is_match):
return pivot # WE FOUND IT!
elif k <= known_low maybe_low len(is_match) and total_size < k known_high maybe_high len(is_match):
return pivot # WE FOUND IT!
# And now place the pivot in the right position.
if pivot_pos == 'right':
known_high = maybe_high len(is_match)
# And put back the left side of each nonemptied array.
for q in (to_process, no_pivot):
while 0 < len(q):
a, low, high, orig_low, orig_high = q.popleft()
if orig_low <= high:
in_flight.append((a, orig_low, high))
while 0 < len(is_match):
a, low, mid, high = is_match.popleft()
if low < mid:
in_flight.append((a, low, mid-1))
else:
known_low = maybe_low len(is_match)
# And put back the right side of each nonemptied array.
for q in (to_process, no_pivot):
while 0 < len(q):
a, low, high, orig_low, orig_high = q.popleft()
if low <= orig_high:
in_flight.append((a, low, orig_high))
while 0 < len(is_match):
a, low, mid, high = is_match.popleft()
if mid < high:
in_flight.append((a, mid 1, high))
list1 = [2,3,6,7,9]
list2 = [1,4,8,10]
list3 = [2,3,5,7]
print(list1, list2, list3)
for i in range(1, len(list1) len(list2) len(list3)):
print(i, kth_of_sorted(i,[list1, list2, list3]))
uj5u.com熱心網友回復：
一般的解決方案是使用最小堆。如果您已經n對陣列進行了排序并且想要第 k 個最小的數字，那么解決方案是 O(k log n)。
這個想法是將每個陣列中的第一個數字插入到最小堆中。插入堆時，插入一個包含數字的元組，以及它來自的陣列。
然后，您從堆中洗掉最小值，并從該值所在的陣列中添加下一個數字。你這樣做 k 次以獲得第 k 個最小的數字。
有關總體思路，請參見https://www.geeksforgeeks.org/find-m-th-smallest-value-in-k-sorted-arrays/。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505870.html
下一篇：高效線段-三角形相交