我遇到了這樣一個面試問題：
一個地區有工廠生產污染氣體，每個工廠都安裝過濾器以減少污染。安裝的每個過濾器都會使該工廠的污染減少一半。每個工廠可以有多個過濾器。有一個包含 N 個整數的串列，表示該地區 N 個工廠中每個工廠的污染程度。找出將總污染減半所需的最少過濾器數量。
例如 - 讓 [3, 5, 6, 1, 18] 是 5 個工廠的污染水平串列
總體污染 = 3 5 6 1 18 = 33（目標是 33/2 = 16.5）
根據 index=4 在工廠安裝過濾器 --> 污染級別將是 [3, 5, 6, 1, 9]
根據 index=4 在工廠安裝過濾器 --> 污染等級將為 [3, 5, 6, 1, 4.5]
根據 index=2 在工廠安裝過濾器 --> 污染等級將為 [3, 5, 3, 1, 4.5]
最少需要 3 個過濾器才能減少總污染的一半。
N 是 [1....30,000] 范圍內的整數。串列中的每個元素都是 [0....70,000] 范圍內的整數
我為此提出的解決方案很簡單：在串列中查找最大值，每次查找一半，直到總和為 <=target
def solution(A):
total = sum(A)
target = total/2
count = 0
while total>target:
count =1
max_p = max(A)
total-= max_p/2
A.remove(max_p)
A.append(max_p/2)
return count
這很好用，除了時間復雜度似乎是 O(N^2)。有人可以建議一種時間復雜度較低（最好是 O(N)）的方法來解決這個問題嗎？
uj5u.com熱心網友回復：
也許您可以利用最大堆來比現在更有效地檢索最差的工廠，即，使用堆將允許O(N log N)解決方案：
import heapq
def filters_required(factories: list[int]) -> int:
"""Returns minimum filters required to halve pollution."""
current_pollution = sum(factories)
goal_pollution = current_pollution / 2
filters = 0
factory_pollution_max_heap = [-p for p in factories]
heapq.heapify(factory_pollution_max_heap)
while current_pollution > goal_pollution:
worst_factory = heapq.heappop(factory_pollution_max_heap)
pollution = worst_factory / 2
current_pollution = pollution # Use = since pollution will be a negative number.
heapq.heappush(factory_pollution_max_heap, pollution)
print('DEBUG:', [-p for p in factory_pollution_max_heap], current_pollution)
filters = 1
return filters
def main() -> None:
print(f'{filters_required(factories=[3, 5, 6, 1, 18]) = }')
if __name__ == '__main__':
main()
輸出：
DEBUG: [9.0, 6, 3, 1, 5] 24.0
DEBUG: [6, 5, 3, 1, 4.5] 19.5
DEBUG: [5, 4.5, 3, 1, 3.0] 16.5
filters_required(factories=[3, 5, 6, 1, 18]) = 3
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/475516.html