最小唯一数组总和

Question

我得到了一道面试题，我的算法只通过了给定的测试案例，没有通过所有的测试案例。

问题：给定一个已排序的整数数组，返回将重复元素变为唯一元素所需添加的数字的和，使得这些唯一元素的和最小。

也就是说，如果数组中的所有元素都是唯一的，则返回它们的和。 如果有一些元素是重复的，则增加它们的值以确保所有元素都是唯一的，并使得这些唯一元素的和最小。

以下是一些示例：

• input1[] = { 2, 3, 4, 5 } => return 19 = 2+3+4+5（所有元素都是唯一的，因此只需将它们相加）
• input2[] = { 1, 2, 2 } => return 6 = 1+2+3（索引2重复了，因此需要将其增加）
• input3[] = { 2, 2, 4, 5 } => return 14 = 2+3+4+5（索引1重复了，因此需要将其增加）

这三个示例都是问题中的示例，我的简单算法如下，通过了这三个示例，但未能通过我看不到输入的其他情况。

static int minUniqueSum(int[] A) {
    int n = A.length;


    int sum = A[0];
    int prev = A[0];

    for( int i = 1; i < n; i++ ) {
        int curr = A[i];

        if( prev == curr ) {
            curr = curr+1;
            sum += curr;
        }
        else {
            sum += curr;
        }
        prev = curr;
    }

    return sum;
}

我不能看到这个算法失败的其他输入。 我能想到一些其他的输入示例：

{1, 1, 1, 1}  --> {1, 2, 3, 4}
{1, 1, 2, 2, 3, 3, 3} --> {1, 2, 3, 4, 5, 6, 7}

{1, 2, 4, 4, 7, 7, 8} --> I think this should be {1, 2, 3, 4, 6, 7, 8}  and my algorithm fails in this example because my algorithm has {1, 2, 4, 5, 7, 8, 9} whose sum is not minimum 

有哪些其他测试用例和算法可以通过所有案例？

有些人抱怨这个问题不清楚。我想让你知道问题所在。关于添加的数字是否只允许正数或正数和负数，没有明确的描述。给定三个带输入输出的例子以及一些其他不允许您查看的输入输出案例，请编写一个程序来通过所有其他未见输入/输出案例。这就是问题所在。

- user2761895

---

在你的最后一个测试用例中，你从第二个索引位置移除了1。然而，在你的问题中，你说只能通过“添加最小数量的重复数字”来使它成为唯一的。 - MathBunny

如果只允许添加数字，如何将 {1, 2, 4, 4, 7, 7, 8} 转化为 {1, 2, 3, 4, 6, 7, 8}？ - tobias_k

只要数组保持排序，就可以添加负数吗？ - stark

一个测试用例可能是一个 int，它位于 Integer 的最大范围内。这会导致溢出。在增量之前，您可能需要将其上转型为 long 以避免这种情况发生。您的总和很可能还需要是 big int 或 double。 - Kenny Steegmans

Answer 1

你的算法在存在更多重复数值的情况下会出现错误，例如：

2, 2, 2

使用你的算法会得到7而非9。

一种最简单的修复方法是：

static int minUniqueSum(int[] A) {
    int n = A.length;

    int sum = A[0];
    int prev = A[0];

    for( int i = 1; i < n; i++ ) {
        int curr = A[i];

        if( prev >= curr ) {
            curr = prev+1;
        }
        sum += curr;
        prev = curr;
    }

    return sum;
}

正如评论中指出的那样，没有必要对已排序的数组进行排序。

- Amit

---

@kremzeek，你的例子没有排序。 - Amit

Answer 2

在 JavaScript 中

var list = [1, 1, 1, 10, 3, 2];

function minUniqueSum(arr) {
  const temp = arr.reduce((acc, cur) => {
    while (acc.includes(cur)) cur++;
    acc.push(cur);
    return acc;
  }, []);
  console.log(temp); // [1, 2, 3, 10, 4, 5]
  return temp.reduce((acc, cur) => acc + cur, 0);
}

var result = minUniqueSum(list);
console.log(result); // 25

- Ricardo Canelas

Answer 3

我这样做了，没有排序。

    // Complete the getMinimumUniqueSum function below.
static int getMinimumUniqueSum(int[] arr) {

 int sum = 0;

 ArrayList < Integer > arrayList = new ArrayList < Integer > (arr.length);

 arrayList.add(arr[0]);


 for (int i = 1; i < arr.length; i++) {

  int val = arr[i];

  while (arrayList.contains(val)) {

   val++;
  }

  arrayList.add(val);

 }



 for (int i = 0; i < arrayList.size(); i++) {
  sum += arrayList.get(i);
 }

 return sum;
}

它通过了所有（13）个测试用例。

- CursedChico

---

给定一个已排序的整数数组，您不需要进行排序并且使用Collection.contains()会过度消耗资源。Arraylist.contains()对性能有害。 - greybeard

Answer 4

// 1,1,2,3 -> 1,2,2,3 -> 1,2,3,3 -> 1,2,3,4 => 10
// 2,2,2 -> 2,3,2 -> 2,3,3 -> 2,3,4 => 9
public int calculateMinSumSorted(int[] input) {
    int sum = input[0];
    for (int i = 1, v = sum; i < input.length; v = input[i++]) {
        if (input[i] <= input[i - 1]) {
            input[i--] = ++v;
        } else {
            sum += input[i];
        }
    }
    return sum;
}

- Oleks

Answer 5

虽然这个解决方案基于Java，但是思路可以应用在任何地方。

你的解决方案几乎是正确的和优化的。使用多个for循环会大大降低速度，因此应该尽可能避免使用！由于您的数组已经预排序，因此您只需要一个for循环就足够了。

您认为最后一个测试用例是错误的并不正确，因为增量意味着您只能执行+1（实际上大多数问题仅限制此分配为增量）。

您错过的是整数的最大范围。

如果他们传递Integer.MAX_VALUE，您的总和将溢出并变为负数。因此，您的总和变量需要更大的类型。double或BigInteger应该可以使用（最好使用BigInteger）。

此外，当他们两次通过MAX_VALUE时，您的curr + 1也会溢出并变为负数。因此，您希望您的curr和prev也是较大的类型。long应该可以做到这一点。

 public static double calculateMinSumSorted(int[] input){
    double sum = input[0];

    long prev = input[0];
    long cur;

    for(int i = 1 ; i < input.length ; i++){
        cur = input[i];
        if(cur <= prev){
            cur = ++prev;
        }
        prev = cur;
        sum += cur;
    }
    return sum;
}

这是我使用的一些测试用例：

@Test
public void testSimpleArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,3,4});
    Assert.assertEquals(10, test1, 0.1);

}
@Test
public void testBeginningSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{2,2,3,4});
    Assert.assertEquals(14, test1, 0.1);
}
@Test
public void testEndingSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,4,4});
    Assert.assertEquals(12, test1, 0.1);
}
@Test
public void testAllSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,1,1,1});
    Assert.assertEquals(10, test1, 0.1);
}

@Test
public void testOverMaxIntResult(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,3,3,4,4,4,4,4,Integer.MAX_VALUE});
    System.out.println(test1);
    Assert.assertEquals(2147483692.0, test1, 0.1);
}

@Test
public void testDoubleMaxIntArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{2,2,3,4,5,6,7,8,9, Integer.MAX_VALUE, Integer.MAX_VALUE});
    Assert.assertEquals(4294967349.0, test1, 0.1);
}

@Test
public void testDoubleMinIntArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE,2,2,3,4,5,6,7,8,9});
    Assert.assertEquals(-4294967241.0, test1, 0.1);
}

- Kenny Steegmans

---

在考虑边界条件和提供单元测试方面做得非常好。缺少（文档）注释，有点啰嗦。我会坚持使用long sum - 长度为n的数组可以由整数0到n-1索引…尝试使用长索引值访问数组组件会导致编译时错误，因此最多有Integer.MAX_VALUE个值为Integer.MAX_VALUE的组件，导致总和约为3/2 Integer.MAX_VALUE² - 在完全准确的范围内。 - greybeard

Answer 6

在C++中：

int64_t getMinimumUniqueSum(std::vector<int> arr)
{
    std::sort(arr.begin(), arr.end());

    int64_t sum = arr[0];
    size_t i = 0;
    size_t j = 1;
    size_t gap_i = j;
    int avail_val = arr[j] + 1;

    while (j < arr.size()) {
        // find next gap with available values
        if (j > gap_i) {
            gap_i = j;
            avail_val = arr[gap_i] + 1;
        }
        while (gap_i < arr.size() && arr[gap_i] <= avail_val) {
            avail_val = arr[gap_i] + 1;
            gap_i++;
        }

        if (arr[i] == arr[j]) {
            // update duplicated value
            arr[j] = avail_val;
            avail_val++;
        } else {
            // move index of prev value - i
            i = j;
        }

        sum += arr[j];
        j++;
    }

    return sum;
}

使用哈希集的直接解决方案将会慢很多：

int64_t getMinimumUniqueSum_Slow(std::vector<int> arr)
{
    std::unordered_set<int> s;

    int64_t sum = 0;

    for (int a : arr) {
        while (s.find(a) != s.end()) {
            a++;
        }
        s.insert(a);
        sum += a;
    }

    return sum;
}

慢速版本需要大约10秒来处理包含10^5个数字的数组。

而优化版本则需要大约0.5秒来处理包含10^7个数字的数组。

但是，虽然缓慢的解决方案显然是正确的——我们可以将其用于对优化方案进行测试：

std::vector<int> random_vec(size_t size, int min_val, int max_val)
{
    std::random_device rnd_device;
    std::mt19937 mersenne_engine {rnd_device()};
    std::uniform_int_distribution<int> dist {min_val, max_val};

    auto gen = [&dist, &mersenne_engine](){
                   return dist(mersenne_engine);
               };

    std::vector<int> arr(size);
    generate(begin(arr), end(arr), gen);

    return arr;
}

int main()
{
    for (int i = 0; i < 1000; i++) {
        printf("%d\n", i);
        auto arr = random_vec(i*10+1, -5, 5);

        int64_t x = getMinimumUniqueSum(arr);
        int64_t y = getMinimumUniqueSum_Slow(arr);
        if (x != y) {
            printf("Results not match: fast -> %lld, slow -> %lld !!!\n\n", x, y);
            return 1;
        }
    }

    return 0;
}

- Aleksei Gutikov

Answer 7

根据您对隐藏I/O的描述，这可能是一道HackerRank测试题。更好的陈述问题的方式是：“给定一个排序后的数字数组，通过增加它们（每次num++）使数字不同，以使数组总和最小化。”

该问题仅允许增量即每次将数字增加1。这也确保了数组始终保持排序状态。 所以{1, 2, 4, 4, 7, 7, 8} --> {1, 2, 4, 5, 7, 8, 9}

这里是问题及其解决方案。 https://www.geeksforgeeks.org/making-elements-distinct-sorted-array-minimum-increments/

- prashant

Answer 8

公共的静态整型 minSum(int arr[]) 函数：

    for(int i=0; i<arr.length-1;i++){

        if(arr[i]==arr[i+1]){

            arr[i+1]= arr[i+1]+1;
        }
    }

    int sum=0;

    for(int i=0; i<arr.length;i++){

        sum=sum+arr[i];
    }

    System.out.println("sum: "+sum);
    return sum;
}

- Kunal Gaurav

Answer 9

int a[] = {1,2,2,3,5,6,6,6,6 }; So what would be elements in array for sum
As per above problem statement it would be {1,2,3,4,5,6,7,8,9 }

Solution
public static void uniqueSum(){
        int a[] = {1,2,2,3,5,6,6,6,6 };
        int n = a.length;
        int sum = a[0];
        int prv=a[0];
        for(int i=1; i<n;i++){
            int cur = a[i];
            if(cur==prv){
                cur = cur+1;
                sum+= cur;
                System.out.print("--"+cur);
            }else{
                if(cur<prv){
                    cur = prv +1;
                }
                sum += cur;
            }
            prv = cur;
        }
        System.out.println("===================== "+sum);
    }

- Rajeev Rathor

Answer 10

如果你可以将负值添加到任何输入中，则最小值仅为数组元素数量N的第N个三角数。 （我假设我们只处理调整过的数组的正数，否则我们可以使它任意小（负数）。

因此，您的算法只需要寻找一对连续的相同值。如果未找到，请返回总和else N *（N +1）/ 2 。

---

如果只有重复元素可以被调整，那么方法就是找到连续元素之间的空隙，并用之前“排队”的值填充它们。 “排队”元素的实际值无关紧要，只需要一个计数器即可。下面是一个C#解决方案，我假设对元素的调整必须是正值。这意味着我们不能向后填充未使用的空洞，从而简化了问题。

int F()
{
    int[] a = {2, 2, 2, 3, 8, 9}; // sorted list

    int n = 0; /* num */   int p = 0; /* prev; zero is an invalid value in the list */
    int q = 0; /* queue */ int s = 0; /* sum */

    for (int i = 1; i < a.Length; i++)
    {
        n = a[i];
        if (n == p)
            q++; // increment queue on duplicate number
        else
        {
            // for every hole between array values, decrement queue and add to the sum
            for (int j = 1; q > 0 && j < n - p; j++, q--)
                s += p + j;
            s += (p = n);
        }
    }
    // flush the queue
    for (; q > 0; q--)
        s += ++n;

    return s;
}

---

你的例子 {1, 2, 4, 4, 7, 7, 8} 表明之前的假设是不成立的。因此，我写了一个使用队列来存储跳过的空洞以便稍后填充的版本。它并不是非常痛苦，而且结构非常相似，但对于大多数面试来说可能仍然太复杂了。

using System.Collections.Generic;
int F2()
{
    int[] a = {1, 1, 8, 8, 8, 8, 8}; // sorted list

    int n = 0; /* num */   int p = 0; // prev; zero is an invalid value in the list
    int q = 0; /* queue */ int s = 0; // sum
    Queue<int> h = new Queue<int>(); // holes

    for (int i = 1; i < a.Length; i++)
    {
        n = a[i];
        if (n == p)
            q++; // increment queue on duplicate number
        else
        {
            for (int j = 1; j < n - p; j++)
                if (h.Count <= q + a.Length - i) // optimization
                    h.Enqueue(p + j);
            s += (p = n);
        }
    }
    // flush the queue
    for (; q > 0; q--)
        s += h.Count > 0 ? h.Dequeue() : ++n;

    return s;
}

在这里尝试它们：http://rextester.com/APO79723

- shawnt00

---

你是对的，问题没有明确说明“数字”是什么，所以我们可以假设它为负数（就像你所做的那样），然后添加例如IEEE 754的“负无穷大”或最小实数双精度浮点数，或者如果限制为正值，则添加到下一个最小的浮点数等差值。但是，你的答案有缺陷，例如如果只有一个重复的数字[1,5,5,9]，你只能修改其中一个“5”的元素，这将不允许填充其他的“空洞”，因此总和不可能是N * (N + 1) / 2。 - le_m

@le_m 这个问题没有明确指定哪些值可以被修改。"添加一些数字"有点不清楚，我在我的答案中确实提到了这个假设。 - shawnt00

@le_m 你说得对。我当时关注的是下面的重新陈述。但正如所指出的，我并不确定，所以我表达了我的假设。 - shawnt00

没错，整个问题并不是很清楚，需要进行分解 - 在面试过程中可能不是最好的做法，但是谁会想为一个连问题都问不清楚的雇主工作呢？ :) - le_m

@le_m 没错！至少你早点发现了。 - shawnt00