arrays - 从 n 个数的数组中选出 m 个数，使它们的总差最小

Question

在一座古城中，有 n 座塔楼，楼层数不定。我们必须在它们上面 build 地板，以便 n 个塔中至少有 m 个(n>=m)高度相同。编写一个函数来计算要使 m 层楼的高度相等，最少需要 build 多少层楼。

示例:给定一个数组 (1,5,4,2,1)，每个元素代表该塔的楼层数且 m=3，该函数应返回 2，因为我们必须在每个塔上 build 1 层索引 0 和 4，所以 3 个塔的高度相同。函数定义如下

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

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. 从元素 2 开始遍历数组。为每个元素 i 计算值:current = current - (arr[i-1] - arr[i])*(m-1 ) + arr[i]-arr[i+m-1]。如果小于它，则保存到 best。

排序的时间复杂度为 O(n*log(n)) + 步骤 2-3 的时间复杂度为 O(n)。