2

1 つの数字を除く 1 ～ 1000 のすべての数字を含む 999 個のセルを含む配列があるとします。この数を見つけるための最も効率的な方法は何ですか? O(n 二乗) よりも良い方法を見つけることができませんでした。インタビュアーは、もっと良い方法があると私に言いました。どうすればできますか？

ソートされていない配列。

4

3 に答える 3

13

1 から 1000 までのすべての数値の合計は、既知の値です。配列内の数値の合計を計算し、その 2 つを引いて差を出します。

from 1..n の合計は です n(n+1)/2。これは数学ではかなり一般的な結果ですが、慣れていない場合は、さまざまな手法を使用して自分で導き出すことができます。

したがって、配列内の数値を合計し、その値を上記の値から差し引くだけで、何が欠けているかがわかります。

コードでは、これは次のようになります。

int findMissing(int [] inputArray) {
    //In the above scenario, inputArray.size() would be 999
    int range = inputArray.size() + 1;   //so, range is 1000
    int expected = range * (range + 1) * 0.5;  //we expect the sum to be 500,500
    int sum = 0;
    for (int x: inputArray) {
       sum += x;
    }
    //the missing number is the difference between what we expected, and what we found
    return expected - sum;

これは O(n) の結果になります。

于 2013-03-11T17:14:02.100 に答える
3

そのように：

 int sum = (1000 * 1001) / 2; // sum of the n first integers is: n*(n+1)/2
 for(int i : array) {
    sum -= i;
 }
 return sum;
于 2013-03-11T17:15:43.567 に答える
2

合計http://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/を使用 して、合計からすべてのセルの合計を差し引くことができます。

missingDigit = (Summation - totalFromCells);
于 2013-03-11T17:18:42.497 に答える