1

我被要求实现一个算法,该算法将以下内容作为输入:

- 整数 a 的排序数组,例如 a=[0,0,0,0,0,2,4,4,4,4,4]。如果它有帮助,则将实际输入作为两个数组给出,第一个给我们整数,第二个给我们第一个整数的每个整数出现的次数。对于我们的示例 [0,2,4],[5,1,5]。

- 整数 k。

并返回一个由唯一实数组成的数组 b(两位小数),其连续元素至少相差 k 且最大差异 |a[i]-b[i]| 是可能的最小值。数组 a 和 b 都已排序。

到目前为止,如前所述,我已经将两个给定的数组合二为一,并且在几个循环之后设法使数组 a 成为具有唯一元素的排序数组,步骤如下:

- 对于整数的每次多次出现,例如 5 次 0 ,我将它们移动最小可能的距离:假设 k=2 然后 [0,0,0,0,0]->[-4,-2,0, 2,4]。

- 然后我对数组进行排序,以找到由移位引起的多个外观。

- 重复这两个步骤,直到数组只有唯一元素。如果我有办法将最后一个数组的元素移动到他们请求的位置(所以他们的最终差异是 >=k),我假设后者与起始数组的差异将由我请求的班次决定。

我的整个想法可能是错误的或太慢了,但我已经在这个问题上走到了死胡同,所以任何帮助都会很棒!先感谢您 !!!

PS我包括一个练习的小例子,使整个事情更清楚:K=2, a=[0,1], b=[3,1] (->c= [0,0,0,1] ) 所以我们的结果应该是 [-2,5 , -0,5 , 1,5 , 2,5] 这使得最大最小移位为 2,50。

4

1 回答 1

0

如果max-min <= k*n, 那么数组b

M+0, M+k, M+2k, ..., M+(n-1)k

哪里M满足

|max-M-k(n-1)| = |min-M|. 

a只要您的连续数组b元素不同,您需要关心的是数组的第一个和最后一个元素,k并且在这种情况下它们必须获得最佳结果。

如果max-min > k*n那么它更容易:设置

k=(max-min)/(n-1)  

满足您条件中的小数位数并设置b[0]=min. 添加k到 的每个下一个元素b

于 2012-11-23T03:48:45.763 回答