12

我在试图解决这个问题时遇到了很多麻烦，而这个麻烦的根源是创建了一个O(n)复杂的算法。这是我正在努力解决的问题：

一个A长度数组n包含范围内的整数[0, .., n - 1]。但是，它只包含n - 1不同的数字。因此，其中一个数字丢失，另一个数字重复。编写一个 Java 方法，将A其作为输入参数并返回缺失的数字；该方法应该在O(n).

例如，什么时候A = [0, 2, 1, 2, 4]，oddOneOut()应该返回3；什么时候A = [3, 0, 0, 4, 2, 1]，oddOneOut()应该回来5。

显然，这是一个很容易用算法解决的问题，（而且很可能，我只是没有看到它！）。我试图用各种方法解决它，但无济于事。我正在尝试用 Java 来解决它，但如果你更愿意用 Python 来解决它，那也可以。O(n2)O(n)

先感谢您...

4

4 回答 4

34

假设缺少的数字是x，重复的数字是y。如果将所有数字相加，总和将是：

(n - 1) * n / 2 - x + y

从以上可以发现(x - y).....(1)

同样，对数字的平方求和。那么总和将是：

(n - 1) * n * (2 * n - 1) / 6 - x2 + y2

从上面你得到....（2）(x2 - y2)

(2) / (1) gives (x + y).....(3)

(1) + (3) 给出2 * x，因此您可以找到x和y。

请注意，在这个解决方案中有O(1)额外的存储空间并且是O(n)时间复杂度。上面的其他解决方案是不必要O(n)的额外存储。

混合 C/C++ 中的代码更清晰：

#include <stdio.h>

int findDup(int *arr, int n, int& dup, int& missing)
{
    int sum = 0;
    int squares = 0;

    for (int i = 0; i < n; i++) {
        sum += arr[i];
        squares += arr[i] * arr[i];
    }

    sum = (n - 1) * n / 2 - sum; // x - y

    squares = (n - 1) * n * (2 * (n - 1) + 1) / 6 - squares; // x^2 - y^2

    if (sum == 0) {
        // no duplicates
        missing = dup = 0;
        return -1;
    }
    missing = (squares / sum + sum) / 2; // ((x^2 - y^2) / (x - y) + (x - y)) / 2 = ((x + y) + (x - y)) / 2 = x

    dup = missing - sum; // x - (x - y) = y

    return 0;
}


int main(int argc, char *argv[])
{
    int dup = 0;
    int missing = 0;

    int a[] = {0, 2, 1, 2, 4};

    findDup(a, sizeof(a) / sizeof(int), dup, missing);
    printf("dup = [%d], missing = [%d]\n", dup, missing);

    int b[] = {3, 0, 0, 4, 2, 1};
    findDup(b, sizeof(b) / sizeof(int), dup, missing);
    printf("dup = [%d], missing = [%d]\n", dup, missing);

    return 0;
}

输出：

dup = [2], missing = [3]
dup = [0], missing = [5]

一些python代码：

def finddup(lst):
    sum = 0
    sumsq = 0
    missing = 0
    dup = 0
    for item in lst:
        sum = sum + item
        sumsq = sumsq + item * item
    n = len(a)
    sum = (n - 1) * n / 2 - sum
    sumsq = (n - 1) * n * (2 * (n - 1) + 1) / 6 - sumsq
    if sum == 0:
        return [-1, missing, dup]
    missing = ((sumsq / sum) + sum) / 2
    dup = missing - sum
    return [0, missing, dup]

found, missing, dup = finddup([0, 2, 1, 2, 4])
if found != -1:
    print "dup = " + str(dup) + " missing = " + str(missing)

print finddup([3, 0, 0, 4, 2, 1])

输出：

dup = 2 missing = 3
[-1, 0, 0]
于 2013-10-14T22:39:03.523 回答
16

迭代数组两次：仍然是 O(n)。创建一个临时的布尔数组（或 Java BitSet）来保存你得到的数字。第二次执行循环时，检查布尔数组中是否有洞。

于 2013-10-14T22:27:35.680 回答
4

使用哈希集并单次通过来检测哪个数字是重复的。在同一迭代期间，跟踪所有数字的累积和。

如果所有数字都不同，现在计算预期总数：n * (n - 1) / 2。减去你找到的总数。您将留下“缺失”的数字减去重复的数字。将副本添加回来以获得您的答案。

由于哈希表访问是常数时间，并且我们使用单次传递，因此这是O(n). （请注意，单次传递并不是绝对必要的：Martijn 指出固定次数的传递仍然是线性复杂度是正确的。）

于 2013-10-14T22:33:18.617 回答
1

这可能很有趣，尽管我不确定它在什么条件下（如果有的话）表现最好。我们的想法是，我们要将每个元素移动到数组中的正确位置（0到索引 0 等），直到清楚什么是缺失的，什么是多余的。

def findmissing(data):
    upto = 0
    gap = -1
    while upto < len(data):
        #print data, gap
        if data[upto] == upto:
            upto += 1
            continue
        idx = data[upto]
        if idx is None:
            upto += 1
            continue
        data[upto], data[idx] = data[idx], data[upto]
        if data[upto] == data[idx]:
            print 'found dupe, it is', data[upto]
            data[upto] = None
            gap = upto
            upto += 1
        elif data[upto] is None:
            gap = upto
    return gap

if __name__ == '__main__':
    data = range(1000)
    import random
    missing = random.choice(data)
    print missing
    data[missing] = data[0]
    data[0] = random.choice(data[1:])
    random.shuffle(data)
    print 'gap is', findmissing(data)

这是 O(n)，因为每一步要么增加一个值，upto 要么将一个值移动到数组中的“正确”位置，而这些事情中的每一个都只能发生n几次。

于 2013-10-14T23:25:21.993 回答