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

我遇到了这样一个面试问题:

某地区有工厂产生污染气体,每个工厂都应安装过滤器以减少污染。安装的每个过滤器都会使该工厂的污染减少一半。每个工厂可以有多个过滤器。有一个包含 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))的方法来解决这个问题吗?

stack overflow 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)
原文答案
author avatar

接受的答案

也许您可以利用 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

答案:

作者头像

我在 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;
}
作者头像

为上述代码编写主代码以简化测试..

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];
    }
    }
}