最小唯一数组和

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

*正如评论中指出的那样,无需对已排序的数组进行排序.