我有兩個排序陣列，我想知道如何列出陣列 1 中大于陣列 2 中的數字的計數。
例如，[1,4,6,8] 和 [4,6,7,9] 將回傳 4，因為 6 大于 4 而 8 大于 4,6,7。目前我能做到這一點的最好方法是在 O(n^2) 中回圈遍歷每個陣列，但是我不確定如何在 O(n) 中做到這一點
uj5u.com熱心網友回復：
使用兩個指標就足夠了，因為陣列是排序的。這個邏輯類似于 Merge Sort 的合并步驟，我們只是在這里跟蹤元素的數量。
時間復雜度：O(N)
a = [1,4,6,8]
b = [4,6,7,9]
l,r = 0,0
n,m = len(a), len(b)
ans = 0
while l<n and r<m:
if a[l]>b[r]:
ans = n-l
r = 1
else:
l = 1
print(ans)
uj5u.com熱心網友回復：
您可以使用two-pointer technique，我們可以保留兩個指標 -p1在第一個串列和p2第二個串列中。我們繼續遞增p1，直到p1inlist1處的數字小于 in 處的p2數字list2。否則，只需將計數增加我們右邊的元素數p1
def smaller_count(list1, list2):
l1, l2, ans = len(list1), len(list2), 0
# pointers in list1 and list2
p1, p2 = 0, 0
while p1 < l1 and p2 < l2:
if list1[p1] > list2[p2]:
ans = l1 - p1
p2 = 1
else:
p1 = 1
return ans
>>> smaller_count([1,4,6,8], [4,6,7,9])
4
>>> smaller_count([1,4,6,8], [0])
4
>>> smaller_count([1,4,6,8], [10])
0
>>> smaller_count([1,4,6,8], [0, 1, 2, 3])
13
由于我們只對這兩個串列進行一次迭代，因此復雜度為O(len(list1) len(list2))
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/427979.html
標籤：算法
上一篇：如何評估這個決議樹的最終結果？