0

以下の値を含むテキストファイルに値を生成するシステムがあります

行 1 : 可能な合計値

2行目：配列の要素数

行 3 (必要に応じて追加行) : 数字自体

私は現在、配列の最初の整数から合計値を減算し、残りの配列を検索して、ペアが見つかるまで同じことを行うアプローチを考えています。

もう 1 つの方法は、順列と組み合わせに基づいて配列内の 2 つの整数を加算し、ペアを見つけることです。

私の分析によると、反復回数を削減するため、最初のソリューションの方が優れています。私の分析はここで正しいですか?他にもっと良いアプローチはありますか?

編集：より明確にするためにここにサンプルを示します 1行目：200行2 = 10行3：10 20 80 78 19 25 198 120 12 65

ここでの有効なペアは 80,120 です。合計すると 200 になり (入力ファイルで可能な合計値として 1 行目に表されます)、配列内のそれらの位置は 3,8 になるためです。最初の要素を取り、可能な合計値でそれを減算し、基本的な検索アルゴリズムを使用して他の要素を検索します。

ここの例を使用して、最初に 10 を取り、それを 200 で減算すると 190 が得られます。次に 190 を検索します。見つかった場合はペアが見つかり、それ以外の場合は同じプロセスを続けます。

4

2 に答える 2

3

問題は漠然としていますが、特定の数に合計される配列内のペアを探している場合は、O(n)ハッシュ テーブルを使用して平均して実行できます。

配列を反復し、要素ごとに:
(1) テーブルにあるかどうかを確認します。それが - 停止して戻る場合、そのようなペアがあります。
(2) Else:num-elementハッシュ テーブルに挿入します。

一致が見つからずに反復が終了した場合、そのようなペアはありません。

擬似コード:

checkIfPairExists(arr,num):
   set <- new empty hash set
   for each element in arr:
        if set.contains(element):
            return true
         else:
            set.add(num-element)
    return false

「合計すると特定の数になる部分集合は存在するか」という一般的な問題はNP-Hardであり、部分和問題として知られているため、既知の多項式解はありません。

于 2012-11-14T11:52:34.540 に答える
1

合計すると 3 番目の数になるペア (2) の数を見つけようとしている場合、一般的には次のようになります。

for(i=0;i<N;i++)
   for(j=i+1;j<N;j++)
      if(numbers[i]+numbers[j]==result)
         The answer is <i,j>
         end

これは O(n^2) です。ただし、改善することは可能です。

数値のリストがソートされている場合 (O(n log n) 時間がかかる)、次のことを試すことができます。

for(i=0;i<N;i++)
   binary_search 'numbers[i+1:N]' for result-numbers[i]
   if search succeeds:
      The answer is <i, search_result_index>
      end

つまり、各番号をステップ実行し、残りのリストでバイナリ検索を実行して、対応する番号を見つけることができます。これには O(n log n) の時間がかかります。search組み込み関数は O(n) 時間でリストをたどって O(n^2) 結果になる可能性があるため、自分自身の上に関数を実装する必要がある場合があります。

どちらの方法でも、現在の数値が結果と等しいという特殊なケースを確認する必要があります。

どちらのアルゴリズムも、配列自体が使用する以上のスペースを使用しません。

コーディング スタイルについては申し訳ありません。私は Java にあまり詳しくありません。重要なのはここでのアイデアです。

于 2012-11-14T11:52:19.393 に答える