14

タイトルで述べたように、差がKである要素のペアを見つけたい 

example k=4 and a[]={7 ,6 23,19,10,11,9,3,15}
output should be :
   7,11
   7,3
   6,10
   19,23
   15,19
   15,11

私はSOの以前の投稿を読みました。 「与えられた合計に追加する配列内の数値のペアを見つけてください」

効率的な解決策を見つけるために、どのくらいの時間がかかりますか？時間計算量O(nlogn)ですかO(n)？分割統治法でこれをやろうとしましたが、終了条件の手がかりが得られません...

効率的な解決策に、入力配列の並べ替えと2つのポインターを使用した要素の操作が含まれる場合は、少なくともO(nlogn)...

に解決策をもたらす数学関連のテクニックはありますかO(n)？どんな助けでも大歓迎です。

4

3 に答える 3

22

ハッシュテーブルを使用してO（n）で実行できます。O（n）のハッシュにすべての数値を入れてから、それらすべてをもう一度調べて。を探しnumber[i]+kます。ハッシュテーブルはO（1）で「はい」または「いいえ」を返します。すべての数値を調べる必要があるため、合計はO（n）になります。ハッシュテーブルの代わりに、O（1）設定とO（1）チェック時間が設定されたセット構造が機能します。

于 2012-05-04T14:09:19.660 に答える
6

O（n * Log（n））の簡単な解決策は、配列を並べ替えてから、次の関数を使用して配列を調べることです。

void find_pairs(int n, int array[], int k)
{
  int first = 0;
  int second = 0;
  while (second < n)
  {
    while (array[second] < array[first]+k)
      second++;
    if (array[second] == array[first]+k)
      printf("%d, %d\n", array[first], array[second]);
    first++;
  }
}

このソリューションは、ハッシュテーブルを使用したソリューションとは異なり、余分なスペースを使用しません。

于 2012-05-04T14:56:29.807 に答える
1

O（n）のインデックスを使用して1つのことを行うことができます

  • arr入力リストでインデックス付けされたブール配列を取得します。
  • 整数iが入力リストにある場合は、次のように設定します。arr[i] = true
  • arr次のように、最小の整数から最大の整数まで 全体をトラバースします。
    • インデックスを見つけたら、trueこのiインデックスを書き留めてください。
    • arr[i+k]本当かどうかを確認してください。はいの場合i、i+k数字は必要なペアです
    • それ以外の場合は、次の整数に進みますi+1
于 2012-05-04T14:10:51.530 に答える