我被要求实现一个算法,该算法将以下内容作为输入:
- 整数 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。