O(n)算法找到从1到n(非奇数)的连续整数数组中的奇数输出

Question

我试图解决这个问题时遇到了很多麻烦,而麻烦的根源在于创建一个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解决它,但是如果你更习惯解决它,那也没关系.O(n2)O(n)

先感谢您...

Answer 1

假设缺少的数字是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]

Answer 2

迭代数组两次:那仍然是O(n).创建一个临时的布尔数组(或一个Java BitSet)来保存你得到的数字.第二次执行循环时,检查布尔数组中是否有孔.