在O(N)中，每一步将列表中的项目减半，找出步骤的最小数目为列表中元素之和的一半。

Question

我遇到了一个面试问题，问题是这样的：

在一个地区有生产污染气体的工厂，每个工厂都要安装过滤器，以减少污染。安装的每一个过滤器将使工厂的污染减少一半。每个工厂可以有多个过滤器。这里有一个N个整数的列表，表示该地区每个N个工厂的污染水平。找出最低数量的过滤器，需要一半的整体污染。 例如-让3，5，6，1，18作为5个工厂的污染水平清单。

• 总污染= 3+5+6+1+18 = 33 (目标为33/2 = 16.5)
• 在工厂安装index=4
• 在工厂安装index=4
• 在工厂安装index=2
• 至少需要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))吗？

Answer 1

也许您可以利用最大堆来比现在更有效地检索最糟糕的工厂，也就是说，使用堆将允许使用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

Answer 2

我在Java中的O(N log N)答案：

public static int pollution(double[] factories) {
    int filters = 0;
    double half = 0, currSum = 0, temp = 0;
    PriorityQueue<Double> pq = new PriorityQueue<>(Collections.reverseOrder());

    for (double i : factories) {
      pq.add(i);
      half += i;
    }

    currSum = half;
    half = half / 2;

    while (currSum > half) {
      temp = pq.poll();
      currSum -= temp / 2;
      pq.add(temp / 2);
      filters++;
    }

    return filters;
}

Answer 3

为上述代码编写了主要代码以简化测试。

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public final class PCFiltersCount
{
    public static int pollution(final double[] aFactories)
    {
    int lFilters = 0;
    double lHalf = 0, lCurrSum = 0, lTemp = 0;

    final PriorityQueue<Double> lPriorityQueue = new PriorityQueue<>(Collections.reverseOrder());
    for (double i : aFactories)
    {
        lPriorityQueue.add(i);
        lHalf += i;
    }

    lCurrSum = lHalf;
    lHalf = lHalf / 2;

    while (lCurrSum > lHalf)
    {
        lTemp = lPriorityQueue.poll();
        lCurrSum -= lTemp / 2;
        lPriorityQueue.add(lTemp / 2);
        lFilters++;
    }

    return lFilters;
    }

    public static void main(final String[] args)
    {
    double[][][] l = {
        {{15.0, 19, 8, 1}, {3}},
        {{10, 10}, {2}},
        {{3, 0, 51}, {2}},
        {{9.0, 6, 3, 1, 5}, {4}},
        {{6, 5, 3, 1, 4.5}, {5}},
        {{5, 4.5, 3, 1, 3.0}, {5}},
        };

    for (final double[][] lFactoryData : l)
    {
        int lResult = pollution(lFactoryData[0]);
        System.out.println("for Input: " + Arrays.toString(lFactoryData[0]) + " = " + lResult);
        assert lResult == lFactoryData[1][0];
    }
    }
}