java - O(n) 算法在从 1 到 n(不是奇数)的连续整数数组中找到奇数输出

Question

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

An Array A of length n contains integers from the range [0, .., n - 1]. However, it only contains n - 1 distinct numbers. So one of the numbers is missing and another number is duplicated. Write a Java method that takes A as an input argument and returns the missing number; the method should run in O(n).

For example, when A = [0, 2, 1, 2, 4], oddOneOut() should return 3; when A = [3, 0, 0, 4, 2, 1], oddOneOut() should return 5.

显然这是一个很容易用 O(n<sup>2</sup>) 解决的问题算法，(很可能是 O(n) ，我只是没有看到它!)。我试图用各种方法解决它，但无济于事。我正在尝试用 Java 解决它，但如果您更习惯用 Python 解决它，那也很好。

提前致谢...

Answer 1

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

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

从上面可以找到(x - y) .....(1)

同样，对数字的平方求和。总和将是:

(n - 1) * n * (2 * n - 1) / 6 - x<sup>2</sup> + y<sup>2</sup>

从上面你得到(x<sup>2</sup> - y<sup>2</sup>) ....(2)

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