以最小成本连接 n 根绳子

为了以最小成本连接 'n' 根绳索，你可以使用优先级队列或最小堆。思路是反复选择两根最短的绳索，将它们连接起来，然后将它们的长度之和重新放回堆中。重复此过程，直到堆中只剩下一根绳索，这根绳索的长度就是连接所有绳索的最小成本。

方法一

这种方法利用优先级队列（最小堆）能够以高效的方式在每次移动时选择并连接两根最短的绳索。继续这个过程，直到只剩下一根绳索，这根绳索的长度就是连接所有绳索的最小成本。

算法

Java 代码实现

输出

说明

1. 启动优先级队列（最小堆）

我们创建一个带有绳索长度限制的最小堆式优先级队列。由于优先级队列中的元素按升序排列，因此最短的绳索长度将位于最前面。

2. 将绳索长度嵌入优先级队列

我们遍历绳索长度数组 (ropes)，并使用 offer() 方法将每个绳索长度扩展到最小堆中。

3. 计算连接绳索的总成本

我们定义 totalCost 变量来跟踪整个方法中连接的总成本。我们处于一个循环中，该循环将一直持续到优先级队列中的绳索数量降至两个（minHeap.size() 大于 2）。

4. 将两根最短的绳索连接起来

在循环内部，我们不断地使用优先级队列的 poll 方法移除位于优先级队列前端的两根最短的绳索。变量 rope1 和 rope2 被赋予绳索。

5. 计算新绳索的长度

新绳索 (newRope) 的长度是通过将 rope1 和 rope2 的长度相加来确定的。

6. 将新绳索插入优先级队列

我们通过 offer 方法将新连接的绳索 (newRope) 的长度重新插入优先级队列。

7. 返回总成本

在循环退出后（优先级队列中只剩下一根绳索），我们将 totalCost 作为连接所有绳索的最小成本返回。

时间复杂度

在内存方面，将所有绳索的长度插入优先级队列在统计上需要 O(n log(n)) 的时间，其中 n 代表绳索的数量。这是因为将任何元素添加到大小为 n 的优先级队列中需要 log(n) 的时间，这是由于其内部堆结构的性质所致。循环会不断选择优先级队列中优先级较高的绳索，直到只剩下一根绳索。在循环的每一轮中，我们都有恒定时间性能，例如移除两个最小项并将新项插入优先级队列。在这里，我们在每次迭代中将优先级队列的大小除以 2。因此，我们得到总迭代次数为 O(n)。

因此，运行时复杂度主要取决于绳索长度的排序，这确定了解决方案为 O(n*log(n))。

空间复杂度

我们使用时间线以优先级队列（最小堆）的形式存储绳索长度，这需要 O(n) 空间来容纳所有坡道。

此外，我们还需要两个以上的整数变量（rope1、rope2、newRope、totalCost），程序会不断在内存中操作这些变量。

因此，总空间复杂度为 O(n)。

方法 - 2

解决以最小成本连接绳索问题的另一种方法是通过贪婪算法，它不涉及优先级队列。它的工作原理如下：

• 将绳索长度数组按升序排列。
• 创建一个名为 totalCost 的变量来存储总成本。
• 遍历已排序数组的索引 1。
• 在每一步，将当前绳索长度和前一根绳索长度之和放入 totalCost。
• 重复此操作，直到所有绳索连接完毕。
• 返回最终的 totalCost。

通过排列最短的绳索来降低总成本，可以实现这种方法。因此，通过在一开始对数组进行排序，我们设法在每一步中每次都选择两根最短的绳索进行连接。

Java 代码实现

输出

说明

1. 排序数组：首先将绳索长度数组按升序排列。通过这样做，我们可以在每个阶段选择连接成本最低的两根绳索，从而降低总成本。
2. 初始化变量：创建一个变量 totalCost 来计算总成本。这个因素将根据我们连接的绳索数量而变化。
3. 遍历数组：对于 i 从 1 到排序数组长度 - 1：我们从索引 1 开始，因为绳索必须与前一根绳索进行比较。在每个阶段，将当前绳索长度添加到前一根绳索长度。
4. 更新总成本：将新绳索的长度（当前绳索和前一根绳索之和的结果）添加到 runningCost。这是连接两根绳索所花费的金额。
5. 更新当前绳索长度：连接两根绳索后，用新绳索的长度修改当前绳索。这会保持排序数组并使用新开发的绳索进行下一次迭代。
6. 返回总成本：所有循环完成后，返回的 totalCost 表示所有连接的最小成本。

时间复杂度

使用 Arrays.sort(ropes) 对 N 个元素的绳索数组进行排序，这需要 O(Nlog(N)) 时间。

然后循环执行 N 次（N 代表绳索的数量），每次循环计算总成本。

现在，NlogN 表达式是主导项，因此最终，时间复杂度为 O(N log N)。

空间复杂度

所提出的代码仅使用恒定量的额外空间，而不牺牲输入的大小。因此，该功能将具有 O(1) 的数量级，因为输入中没有大小依赖性。

上述方法之间的差异

1. 复杂度
   • 时间复杂度
     • 方法 1：由于优先级队列操作，时间复杂度为 O(N log N)。
     • 方法 2：由于排序，时间复杂度为 O(N log N)。
   • 空间复杂度
     • 方法 1：由于优先级队列，空间复杂度为 O(N)。
     • 方法 2：仅使用恒定额外空间，空间复杂度为 O(1)。
2. 实施
   • 方法 1：使用优先级队列有效选择和连接绳索。
   • 方法 2：依赖排序和迭代连接，不使用优先级队列。

结论

总之，两种方法都为以最低价格连接绳索的任务提供了方便的解决方案。

绳索排序的时间复杂度为 O(N log N)，因此采用优先级队列最小堆的方法 1 的时间复杂度等于 O(N log N)，并且优先级队列需要 O(N) 的空间复杂度。

方法 2，指的是在没有优先级队列的情况下实现贪婪范式的算法，其时间复杂度与方法 1 没有区别：O(N log N)，这源于排序，但其空间复杂度不同：O(1)，这使得它不需要额外的数据结构。