给定一个整数数组，在java中找到并增加具有最低总数组总和的重复值？

Question

我正在经历一些面试编码练习问题，我偶然发现了以下几点：

问题：

给定一个数组，arr，我们希望它通过增加任何重复元素来使其唯一，从而使唯一元素arr的总和arr最小。换句话说，如果两个或多个元素arr不是唯一的，我们必须将重复元素的值增加到某个其他数字，这样arr由唯一元素组成的数字总和尽可能小.

例如，如果arr = [3, 2, 1, 2, 7], thenarr unique = [3, 2, 1, 4, 7]及其元素总和为 的最小值3 + 2 + 1 + 4 + 7 = 17。

完成 getMinimumUniqueSum 函数。它有一个参数：一个由 n 个整数组成的数组，arr。该函数必须返回一个整数，表示arr唯一元素的总和。

我的第一种方法是使用归并排序对数组进行排序，然后查找重复项并递增它。

  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];

  }

但我真的被困在我必须增加重复值才能得到最低总和的部分。

任何人都可以请帮忙。

谢谢

更新

1. 我的合并排序工作正常，它很好地对数组进行了排序。

2. 我们不允许使用任何内置的 java - 这个练习的目的是从头开始，并测试我们的算法能力。

3. 请记住时间和空间的复杂性。如果可能的话，我试图在 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]到结果变量中。上面的代码片段纯粹是为了确保您拥有独一无二的东西。