从n个数字的数组中选择m个数字，使它们的总差异最小。

Question

在古老的城市中有n座塔楼，每座塔楼的楼层数量不同。我们需要在这些塔楼上建造楼层，以便至少m座塔楼（n≥m）高度相等。请编写一个函数来计算建造最少楼层数，使得m座塔楼高度相等。

例如：给定数组（1,5,4,2,1），每个元素代表该塔楼的楼层数量，且m=3，则该函数应返回2，因为我们需要在索引0和4的塔楼上各建造1层楼，这样就可以有3座塔楼高度相等。以下是函数定义：

public Integer calcMinFloors(Integer[] towers, int m);

- crazyim5

---

“for m floors to be of equal height” 应该是 “为了让m座塔拥有相等的高度”，对吗？另外，“There are m towers” 可能应该是 “There are n towers”。 - Ruslan Bes

请问您能否编辑一下您的问题？我看到了 k、n、m..但是哪个代表什么意思呢？我可以猜测这些变量的含义...但是这样会让人感到困惑，如果读者不需要自己去猜测变量的含义，那就更好了。 - dingalapadum

现在问题已经修复。感谢您的纠正。 - crazyim5

Answer 1

以下是@gnasher729回答的更新：

针对n个元素的数组，有一个简单的解决方案：

1. 按降序排序：(5,4,2,1,1)
2. 循环遍历每个元素，并向前查看接下来的m-1个元素。将差值相加并保存最小值。时间复杂度为 O(n*m)

稍微高级一些的解决方案：

1. 按降序排序：(5,4,2,1,1)
2. 获取第一个元素 (5)，向前查看m-1个元素(4,2)，计算需要多少层楼(1 + 3 = 4)，将结果存储为best和current
3. 从第二个元素开始循环遍历整个数组。对于每个元素i，计算该值：current = current - (arr[i-1] - arr[i])*(m-1) + arr[i]-arr[i+m-1]。如果该值比当前best更小，则将其保存到best中。

这样可以获得时间复杂度为O(n*log(n))（排序）+ O(n)（步骤2-3）。

- Ruslan Bes

Answer 2

这个问题可以在时间复杂度为O(NlogN)，空间复杂度为O(1)的情况下解决，其中N是塔的数量。

我们必须建造等高的m座塔，使得我们需要建造最少的楼层数。

重要观察：

1. 因为我们要建造最少的楼层，而不是在m座塔上建造楼层并达到相同的高度，我们将尝试使m-1座塔具有目标塔的相同高度。

2. 最佳解决方案在于找到这样的m座塔，它们具有最小的高度差之和。让解决方案的塔按以下升序排列：

m1 , m2 , m3 , ....... m floor

最优解具有以下属性：

差值之和最小：

(m - m1) + (m - m2) + (m - m3) + .....(m - (m-1))

只有这样，我们才能说需要建造最少的楼层数。

因此，我们需要找到一组m层楼，使它们与具有最大高度的楼层之间的高度差最小（在这些m座塔中）。

假设我们有长度为n的数组arr，表示每个塔上的楼层数。首先，按照它们的高度对塔进行排序。

然后，我们开始以以下方式计算差异之和。假设我们在索引i处。我们找到以下总和：

arr[i + m - 1] - arr[i]
         +
arr[i + m - 2] - arr[i]
         +
arr[i + m - 3] - arr[i]
         +
arr[i + m - 4] - arr[i]
         .
         .
         .
arr[i + 1] - arr[i]

我们将总和称为s1。现在，当我们考虑下一组包含m个塔的时候，也就是从索引i + 1到i + m的塔，我们不需要循环来计算差值的总和，它可以通过以下公式简单地推导得出:

(m - 1)*arr[i + m] - s1 - ((m-1)*arr[i])

因此，使用这种简单的数学技巧，我们只需要一个for循环来解决这个问题。

所提出算法的伪代码如下：

Sort the array arr of n towers.

Compute the sum of differences for first set of m towers.

sum = 0

for(i = 1 to m - 1)
{
  sum = sum + arr[i] - arr[0]
}

Now for the remaining set of m towers

previous_sum = sum, sum = 0, j = 1
minimum_sum = previous_sum
for(i = m to n - 1)
{

 sum = (m-1)*arr[i] - previous_sum - (m - 1)*arr[j - 1]
 increment j

 if( sum < minimum_sum )
 {
  minimum_sum = sum
 }

 previous_sum = sum
}

The answer is minimum_sum.

- Sumeet

---

@dingalapadum，请告诉我哪个示例是错误的。我会很乐意删除我的回答。 - Sumeet

{1, 5, 5, 5, 5, 5, 5, 5, 5, 6}。m=9 - dingalapadum

对于 Towers = (1, 5, 5, 5, 5, 5, 5, 5, 5, 6) 和 m=9 的情况，正确答案是8。但我仍然不理解解决方案。 - crazyim5

@crazyim5 与其在高度为5的8个塔中每个塔建造1层，我们只在第一个高度为1的塔上建造4层。 - Sumeet

@crazyim5 如何才能得出正确答案是8？请澄清一下。您的问题中存在矛盾之处。 - Sumeet

Answer 3

你可以按照身高升序或降序排序，其余的都很简单。

- gnasher729

---

微不足道的部分的复杂度是多少？直接的方法给出了O(n*m)，有更好的方法吗？ - Ruslan Bes