找到列表中元素总和减半的最小步骤数，其中每个步骤将列表中的项目减半 O(N)

Question

我遇到了这样一个面试题：

There are factories in an area which produce a pollutive gas and filters are to be installed at each factory to reduce the pollution. Each filter installed would half the pollution in that factory. Each factory can have multiple filters. There is a list of N integers representing the level of pollution in each of the N factories in the area. Find the minimum number of filters needed to half the overall pollution.

E.g. - Let [3, 5, 6, 1, 18] be the list of pollution levels in 5 factories

Overall pollution = 3+5+6+1+18 = 33 (target is 33/2 = 16.5)

Install a filter in factory given by index=4 -- > pollution levels will be [3, 5, 6, 1, 9]

Install a filter in factory given by index=4 -- > pollution levels will be [3, 5, 6, 1, 4.5]

Install a filter in factory given by index=2 -- > pollution levels will be [3, 5, 3, 1, 4.5]

Need 3 filters minimum to half the overall pollution.

N is an integer within the range [1....30,000]. Each element in the list is an integer within the range [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)）的方法来解决这个问题吗？

Answer 1

也许您可以利用 max heap 比现在更有效地检索最差的工厂，即，使用堆将允许 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

找到列表中元素总和减半的最小步骤数，其中每个步骤将列表中的项目减半 O(N)

Find the minimum number of steps to half the sum of elements in a list where each step halves an item in the list in O(N)

python

algorithm

factory

time-complexity

data-structures