重複の可能性:
2 つの欠落している数字を見つける
私はしばらく考えていましたが、これに対する答えが得られないようです.配列が与えられます。配列にない 1 から n までの 2 つの整数を O(n) 時間で見つけるにはどうすればよいでしょうか?
たとえば、a = [4,3,1,6] と O(1) 余分なスペース O(n) 時間で 2, 5 を見つけるにはどうすればよいでしょうか?
1576 次
1 に答える
3
ここにアイデアがあります。欠落している数値に関する情報を提供する統計を保持するだけです。たとえば、すべての数値の合計を S として計算すると、次のようになります。
(1+2+..+N) - S = a+b
ここで、a と b は欠損値です。あなたの例では、次のようになります。
1+2+3+4+5+6 - 4+3+1+6 = 7 = a+b
次に、たとえば乗算と取得についても同じことを行うことができます。
(1*2*..*N) / S = a*b
あなたの場合：
(1*2*3*4*5*6) / 72 = 10 = a*b
したがって、答えは 2 と 5 です。
基本的に、この方法で使用できる統計はたくさんあります...
于 2012-10-05T04:46:56.193 に答える