如何降低运送物品的时间复杂度

Question

我的车辆每次行程具有最大承载物品的能力，并且在每次行程中它可以挑选 max_items 个相同类型的物品。 返回车辆所需的最少行程次数。

示例： 我有一个 items 数组，其中 items[i] 表示类型 i 的项目数。

items = [4,4,3]

vehicle capacity per trip = 3

max items same type allowed per trip is 3

output is 3

限制：

n is items list size, 1 <= n <= 10^5

1 <= items[i] <= 10^5

1<= capacity <= 10^5

1 <= max_allowed_same_type <= 10^5

这是我的代码：

public static long solve(List<Integer> items, int capacity, int max_allowed_same_type) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    pq.addAll(items);

    long result = 0;
    while (!pq.isEmpty()) {
        int load = 0;
        while (load < capacity && !pq.isEmpty()) {
            int item = pq.poll();
            int minItem = Math.min(max_allowed_same_type, item);
            int e = load + minItem;
            if (e > capacity) {
                int diff = capacity - load;
                pq.add(item - diff);
                break;
            } else {
                load += minItem;
            }
            if (item > minItem) {
                pq.add(item - minItem);
            }
        }
        result++;
    }
    return result;
}

public static void main(String[] args) {
    // Test case 1
    System.out.println(solve(Arrays.asList(4, 4, 3), 3, 3)); // 4

    // Test case 2
    System.out.println(solve(Arrays.asList(3, 2, 2, 6), 2, 1)); // 7

    // Test case 3 (the one that was failing)
    System.out.println(solve(Arrays.asList(1, 4), 1, 2)); // 5

}

我不确定这段代码的时间复杂度是多少。我假设在最坏的情况下我的代码的复杂度是

O(sum(items))

，如果我错了，请纠正我。以较少的时间复杂度解决这个问题的正确方法是什么。

Answer 1

您使用 PriorityQueue 来获取每次循环迭代中的最大项目。这会增加 log(n) 的复杂性，其中 n 是堆的大小。所以你的算法复杂度应该是 O(s*log(n))，其中 s=sum(items)。然而，在我看来，使用堆是没有意义的。您可以简单地循环遍历项目数组，将每个项目的值减少不超过 max_items，以获得负载与容量的总重量。