12

私はこの問題を解明するのに非常に苦労しており、その問題の根源はO(n)複雑なアルゴリズムを作成することです。これが私が苦労している質問です：

A長さの配列にnは、範囲 の整数が含まれます[0, .., n - 1]。ただし、n - 1個別の番号のみが含まれます。そのため、番号の 1 つが欠落しており、別の番号が重複しています。A入力引数として取り、不足している数値を返すJava メソッドを作成します。メソッドは で実行する必要があり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)

同様に、数値の 2 乗を合計します。合計は次のようになります。

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

上記から、 ....(2)が得られます。(x2 - y2)

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

(1) + (3) が与えられ、それによってとが得2 * xられます。xy

このソリューションには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

配列を 2 回繰り返します。これはまだ O(n) です。ブール値 (または Java BitSet) の一時的な配列を作成して、取得した数値を保持します。2 回目のループで、ブール値の配列に穴がないかどうかを確認します。

于 2013-10-14T22:27:35.680 に答える