这个数组最小化问题的最佳算法是什么？

Question

我有一个大小为 n 的 'A' 数组，其中包含一些不一定不同的数字 {a1, a2, …, an}。我必须创建另一个数组 B = {b1, b2, …, bn} ，它们是不同的，这样的值总和|ai - bi|总的来说 i's{i =1 to i =n} 被最小化了。

基本上我想最小化|ai - bi| 的总和总而言之我

最好的算法是什么？

我尝试了一种贪婪的方法：

伪代码：

for i = 0 to n-1{
 if(a[i] not in b){
  b[i] = a[i];}
 else{
  cnt = 1
  assigned = false
 do{
  if(a[i]-cnt not in b){
   b[i] = a[i]-cnt;
   assigned = true}
  elif(a[i]+cnt not in b){
   b[i] = a[i]+cnt;
   assigned = true}
  else
   cnt++
 }while(assigned==false)
}//else
}//for loop

注意： 'n' 是一个输入变量。目标是最小化 |ai - bi| 的总和总而言之我

Answer 1

我想出了一个 O(NlogN) 的解决方案。它基于对输入序列进行排序并贪婪地扩展它周围的可用数字。

Python中的代码实现：


def get_closest_distinct_tuple(X: list):
    X = sorted(X, reverse=True)
    hmap = {}
    used_set = set()

    Y = []

    for x in X:
        if x not in used_set:
            Y.append(x)
            hmap[x] = 1
            used_set.add(x)
        else:
            Y.append(x + hmap[x])
            used_set.add(x + hmap[x])
            hmap[x] = 1 - hmap[x] if hmap[x] < 0 else -hmap[x]

    dist = sum([abs(X[i]-Y[i]) for i in range(len(X))])
    return dist, Y


print(get_closest_distinct_tuple([20, 1, 1, 1, 1, 1, 1]))

输出：

Dist: 9
Y = [20, 1, 2, 0, 3, -1, 4]

我真的无法找到一种方法来证明这是目前最好的解决方案。

这个数组最小化问题的最佳算法是什么？

What is the best algo for this array minimization problem?

language-agnostic

algorithm

pseudocode

minimization

Python中的代码实现：