algorithm - 用最小的总和制作独特的数组

Question

这是一道面试题。给定一个数组，例如 [3,2,1,2,7]，我们希望通过递增重复元素来使该数组中的所有元素唯一，并且我们要求精化数组的总和最小。例如 [3,2,1,2,7] 的答案是 [3,2,1,4,7]，它的总和是 17。有什么想法吗？

Answer 1

它不像我之前的评论所建议的那么简单，但也不是非常复杂。

首先，对输入数组进行排序。如果能够恢复元素的原始顺序很重要，则记录用于排序的排列。

其次，从左到右(即从低到高)扫描排序好的数组。如果一个元素小于或等于其左侧的元素，则将其设置为比该元素大 1。

伪代码

  sar = sort(input_array)
  for index = 2:size(sar)   ! I count from 1
      if sar(index)<=sar(index-1) sar(index) = sar(index-1)+1
  forend

结果的总和最小吗？我已经说服自己这是通过一些挠头和试验，但我没有得到正式的证据。