給定一個帶有重復項的大型無序串列，我如何找到串列中位于下限和上限之間的值的計數，包括良好的時間和空間復雜度？如果在 python 中有解釋，那就太好了。尋找 O(nlog(n)) 方法
Sample input
5 # number of elements in unordered list
2 4 98 3 100 # unordered list. values in list from 1 to 10 ^7
4 # number of subsequent bounds as input
99 101 # left is lower bound right is upper bound
1 5
100 100
2 2
Sample output
1 # 1 number in list between 99 and 101 inclusive
3 # 3 numbers in list between 1 and 5 inclusive
1
1
uj5u.com熱心網友回復：
不確定這是否是您要查找的內容，但為了找到計數，您可以在串列的間隔中執行類似于以下的操作：
list[start:stop].count(element)
uj5u.com熱心網友回復：
一種方法是迭代串列并將每個值與每組邊界進行比較。這是串列的長度和O(n*m)的長度。除非相對于串列的長度有很多界限，否則這應該低于. 在空間方面，這僅使用附加值。nmboundsO(nlogn)m
ll = [2,4,98,3,100]
bounds = [[99,101], [1,5], [100,100], [2,2]]
result = [0 for _ in range(len(bounds))]
for num in ll:
for i, [upper, lower] in enumerate(bounds):
if upper <= num <= lower:
result[i] = 1
print(result)
輸出：
[1, 3, 1, 1]
uj5u.com熱心網友回復：
用python解決了
- 合并排序串列
- 使用二分查找（二分庫）
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/517806.html
上一篇：估計排序演算法的計算成本