0

配列 A には、範囲 [0, n-1] の n-1 個の一意の整数が含まれます。つまり、この範囲には、A にない数値が 1 つあります。その数値を見つけるための O(n) アルゴリズムを設計します。配列 A 自体以外に O(1) の追加スペースのみを使用できます。

この質問には助けが必要です。

4

3 に答える 3

5
  1. 配列を合計します。
  2. 算術累進式を使用して期待される合計を計算します

これらの値を考えると、一方は0 + 1 + 2 + ... + n-1、もう一方は実際の要素の合計です。それらが互いにどのように異なるか、一方が持っていて他方が持っていないものを考えてください。あなたがそれを知っていることを確認してください、そして答えは簡単です.

編集: (理論的なコメント): ビットが必要
であることに注意してください。したがって、要素がすべて 32 ビットの整数である場合、合計を表すために最大 64 ビットが必要になります。 純粋に理論的なアプローチから - そうではありません。ただし、配列自体 (複数 のビットを含む) を使用して合計を格納できます。sum(array)2*log_2(max(arr))
O(1)2*log_2(max(arr))

于 2012-09-05T13:45:06.617 に答える
1

-1で初期化された追加の変数を使用してから、位置としてtmp使用して配列を並べ替えます。tmpn

function find_missing(array)
begin
  tmp := -1
  i := 0;
  while i<length(array)
    if (array[i] = -1) or (array[i] = i) then
      // either on a cell with the right number or 
      // a candiate for the missing number, just go on
      i := i + 1
    else if array[i] = n then
      // use tmp as the nth cell
      array[i]=tmp
      tmp=n
    else
      // swap the value of the current cell with the value
      // of the cell were the value i should be
      swap(array, i, array[i])
    end if
  end while
end

-1は欠落している番号を指している必要があります。

于 2012-09-05T14:53:55.623 に答える
0

別のアプローチがあります：

  1. 一時変数Numberを0に設定します
  2. 配列内の要素ごとに、Number =NumberXOR要素を設定します
  3. 数値Mごとに、M>NおよびM<2 **（ceil（log2（N））set Number = Number XOR M
  4. 不足している番号は番号です
于 2012-09-06T17:10:32.907 に答える