这个问题可以在时间复杂度为
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.
k
、n
、m
..但是哪个代表什么意思呢?我可以猜测这些变量的含义...但是这样会让人感到困惑,如果读者不需要自己去猜测变量的含义,那就更好了。 - dingalapadum