java - 给定一个整数数组，查找并递增具有Java中总数组最低总和的重复值？

Question

我在经历一些面试编码实践问题时，遇到了以下问题：
问题：
给定一个数组arr，我们希望它通过递增arr中的任何重复元素使其唯一，从而使arrunique的元素之和最小换言之，如果arr中的两个或多个元素不是唯一的，我们必须将重复元素的值增加到一些其他数字，以便arr包含的唯一元素总和尽可能小。
例如，如果arr = [3, 2, 1, 2, 7]，则arr unique = [3, 2, 1, 4, 7]及其元素的总和为最小值3 + 2 + 1 + 4 + 7 = 17。
完成getMinimumUniqueSum函数它有一个参数：n个整数的数组，arr函数必须返回一个整数，表示unique元素的和。
我的第一个方法是使用merge sort对数组排序，然后查找重复项并递增它。

  public void initiateMergeSort(int lowerIndex, int higherIndex) {

    if (lowerIndex < higherIndex) {

      int middle = lowerIndex + (higherIndex - lowerIndex) / 2;

      // sorting left side of the array
      initiateMergeSort(lowerIndex, middle);

      // sorting right side of the array
      initiateMergeSort(middle + 1, higherIndex);

      // merging both sides
      computeMergeSort(lowerIndex, middle, higherIndex);
    }
  }

  private void computeMergeSort(int lowerIndex, int middle, int higherIndex) {

    for (int i = lowerIndex; i <= higherIndex ; ++i) {

      tempMergeArray[i] = defaultArray[i];

    }

    int i, j, k;

    // we initialise i and k to the leftmost side of the array, and j being in the middle of the array
    i = k = lowerIndex;
    j = middle + 1;

    // while i loops from beginning to middle of the array, and j from middle to the end of the array
    while (i <= middle && j <= higherIndex) {

      if (tempMergeArray[i] <= tempMergeArray[j]) {

        defaultArray[k] = tempMergeArray[i];
        i++;

      } else {

        defaultArray[k] = tempMergeArray[j];
        j++;

      }

      k++;
    }

    while (i <= middle) {
      defaultArray[k] = tempMergeArray[i];
      k++;
      i++;
    }
  }

  public void getMinimumUniqueSum(int[] arrUnique) {

    /**
     * Todo:
     *    * get lowest and highest value from the array ✔
     *    * generate lowest unique random number between the range (lowest - highest)
     *    * loop through the array and look for duplicate and assign the unique number
     *    * do above recursively()
     */

    int min = defaultArray[0], max = defaultArray[defaultArray.length - 1];

  }

但我真的陷入了这样一个境地：为了得到最低的和，我必须增加重复的值。
有人能帮忙吗？
谢谢
更新
我的合并排序工作正常，它对数组进行了很好的排序。
我们不允许使用任何java内置代码—本练习的目的是从头开始，测试我们的算法能力。
请记住时间和空间的复杂性。如果可能的话，我想在O（n）中实现这个目标

Answer 1

如果涉及排序，请使用此代码段使数字唯一：

Integer previous = null;
for (int i = 0; i < sortedInts.length; i++)
{
    if (previous != null && previous >= sortedInts[i])
    {
        sortedInts[i] = previous + 1;
    }

    previous = sortedInts[i];
}

之后，你就可以总结了或者，如果希望避免再次迭代数组，可以直接将sortedInts[i]添加到结果变量中。上面的片段纯粹是为了确保你得到uniques。