时间戳

首页 > 解决方案 > C中总和的最小和

c - C中总和的最小和

问题描述

以下是问题的简要说明：

我们得到一个 int 数组。我们需要将数组压缩为单个 int。每次压缩都将两个整数加在一起。从压缩返回的值被推回“需要压缩”组，并添加到所有压缩的运行总和中。因此，目标是在数组完全压缩后获得最小的总和。如果我没有意义，这是一个例子：

————</p> 

To Be Compressed                Runningsum   sum
[5, 12, 9, 15] -> 5 + 9 = 14.         0+14 = 14
[14, 12, 15] -> 14 + 12 = 26.        14+26 = 40
[26, 15] -> 26 + 15 = 41.            40+41 = 81
[41] -> Done

所以这里 81 是解决方案。

————</p>

只是为了完整性。这是一个错误的解决方案：

To Be Compressed                Runningsum   sum
[5, 12, 9, 15] -> 5 + 12 = 17.        0+17 = 17
[17, 9, 15] -> 9 + 15 = 24.          17+24 = 41
[17, 24] -> 17 + 24 = 41.            41+41 = 82
[41] -> Done

所以这里 82 不是总和的最佳总和。

————</p>

我了解如何通过执行双重 for 循环并在每个内部循环的数组中找到下一个最小值来执行此蛮力 O(n^2)。然后在外循环中，将运行总和设置为自身 + 刚刚找到的最小值，然后将运行总和添加到总和中。

    findminimum() //5
runningsum=runningsum + 5
sum=0
    findminimum() //9
runningsum=runningsum + 9  //5+9=14
sum+=runningsum            //0+14=14
    findminimum() //12
runningsum=runningsum + 12 //14+12=26
sum+=runningsum            //14+26=40
    findminimum() //15
runningsum=runningsum + 15 //26+15=41
sum+=runningsum            //40+41=81

return sum

这可行，但显然 O(n^2) 不是最好的。

接下来，您可以对数组进行合并排序。由于数组已排序，我们不必执行第二个 for 循环，即找到上面的下一个 min aka findminimum()。所以我们可以在一个 for 循环中进行 runningsum 和 sum 数学运算。这将是 O(nlog(n))。

所以我的问题是，你们是否都看到了在 O(n) 中执行此操作的任何方法，或者 nlogn 似乎是最好的可能性？可能有一些我不熟悉的数学公式用来解决这个问题。

如果有任何不清楚的地方，我很乐意指定。谢谢你的时间！

标签： carrayssum

解决方案

如果您的最小运行时间确实受到您的排序的限制，那么经典的比较排序最多可以证明您为 O(nlogn)。

关键字有一个“比较”排序。

如果您完全熟悉线性时间排序，那么这些可能对您有用。

例如，此链接描述了所谓的计数排序。

它比我在这里能做的（更好）解释工作。本质上，您分配一个大小为 max(arrtoMinSum) 的数组，然后对于 arrToMinSum 中的每个元素，您在该索引处递增数组值。在对该分配的数组进行累积总和之后，然后遍历原始数组，并使用分配数组中的值作为索引，将原始数组中的每个值存储在最终输出数组中。我强烈建议您通读它，而不是根据我的解释实施。

由于您创建了一个大小为 max(arrToMinSum) 的数组，并遍历它和您的原始数组，因此您的运行时将是O(max(max(arrToMinSum),n). 这（在许多情况下）比比较排序更快，但代价是更高的内存使用率。

推荐阅读