arrays - 最小唯一数组总和

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 

还有哪些测试用例和可以通过所有用例的算法？

有人提示问题不明确。我想让你知道这个问题。没有明确说明加号是只允许正数还是正负数。给定三个带有输入和输出的示例，以及一些您不允许看到的其他输入和输出案例，编写一个程序来传递所有其他看不见的输入/输出案例。就是这个问题。

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

*正如评论中所指出的，不需要对已经排序的数组进行排序。