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

Question

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

某个地区有一些工厂会产生污染气体，每个工厂都要安装过滤器以减少污染。每安装一个过滤器就会使该工厂的污染减少一半。每个工厂可以有多个过滤器。有一个包含 N 个整数的列表，代表该地区 N 个工厂中每个工厂的污染程度。找出将总体污染减半所需的最少过滤器数量。

例如- 设 [3, 5, 6, 1, 18] 为 5 个工厂的污染等级列表

• 总体污染=3+5+6+1+18=33（目标是33/2=16.5）

• 在工厂安装一个索引=4的过滤器 --> 污染级别将是[3, 5, 6, 1, 9]

• 在工厂安装索引=4的过滤器 --> 污染等级将为[3, 5, 6, 1, 4.5]

• 在工厂安装索引=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)）的方法来解决这个问题吗？

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

Answer 4

如果有人想知道 Javascript 的解决方案，这是我的看法。

function filtersRequired(factories) {
  // Returns minimum filters required to halve pollution.
  let currentPollution = factories.reduce((a, b) => a + b, 0);
  const goalPollution = currentPollution / 2;
  let filters = 0;
  const factoryPollutionMaxHeap = factories.map((p) => -p);
  makeHeap(factoryPollutionMaxHeap);

  while (currentPollution > goalPollution) {
    const worstFactory = extractMin(factoryPollutionMaxHeap);
    const pollution = worstFactory / 2;
    currentPollution += pollution;
    insert(factoryPollutionMaxHeap, pollution);
    console.log(
      "DEBUG:",
      factoryPollutionMaxHeap.map((p) => -p),
      currentPollution
    );
    filters += 1;
  }

  return filters;
}

function makeHeap(arr) {
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
    heapify(arr, i);
  }
}

function heapify(arr, i) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let largest = i;

  if (left < arr.length && arr[left] < arr[largest]) {
    largest = left;
  }

  if (right < arr.length && arr[right] < arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, largest);
  }
}

function extractMin(arr) {
  if (arr.length <= 0) {
    return undefined;
  }
  if (arr.length === 1) {
    return arr.pop();
  }

  const root = arr[0];
  arr[0] = arr.pop();
  heapify(arr, 0);
  return root;
}

function insert(arr, val) {
  arr.push(val);
  let currentIdx = arr.length - 1;
  while (currentIdx > 0) {
    const parentIdx = Math.floor((currentIdx - 1) / 2);
    if (arr[parentIdx] <= val) {
      break;
    }
    [arr[currentIdx], arr[parentIdx]] = [arr[parentIdx], arr[currentIdx]];
    currentIdx = parentIdx;
  }
}

function main() {
  console.log(`Filters Required: ${filtersRequired([5, 19, 8, 1])}`);
}

main();