23

これは私が遭遇した一般的な面接の質問ですが、要求された方法でそれを改善できませんでした.

assume we have an int array int[] A, we want to find the first duplicate entry.

  1. ほとんどの人が HashSet の使用を考え、解析中に追加することができます。これにより、O(n) 時間と O(n) スペースが発生します。この後、他のデータ構造なしで解決するように求められました。最もばかげたアイデアは、それぞれを O(n^2) 時間で比較することだと言いました。そして、O(n^2)時間の改善を求められました。

  2. そしてそれを改善するために、固定サイズの配列を使用することを考えました（最大数がnであると仮定）、boolean [] b = new boolean [n]; しかし、私はこの方法を使用することを許可されていませんでした。

  3. 次に、ビット操作を使用して int 変数を使用することを考えました。最大数が 32 より小さい場合、n に対して 1 ～ n ビットを左にプッシュし、| チェッカーに & チェッカーを配列内の次のエントリに移動して、> 0 かどうかを確認します。例:

    int c = A[i];
if(check & (1 << c) > 0) return false;
check |= 1 << c;

ただし、これも許可されていません。

それで、配列自体をハッシュセット/ハッシュテーブル、および「線形ハッシュ」として使用できるというヒントがありましたか?

何か助けはありますか？ありがとう

4

9 に答える 9

4

この目的のために設計された組み込み構造が明らかにあるのに、「他のデータ構造」を使用してほしくない理由をインタビュアーに尋ねますHashSet。

  1. O(n)です。何か本当に巧妙な方法で O(log n) に到達しない限り、他の方法を使用してもおそらくこれよりも優れた結果は得られないでしょう。
  2. これは Java であり、C ではありません。これを行うための簡単に利用できるデータ構造があり、プログラマー側の追加の労力はほとんど必要ありません。

Collections Framework の Java ドキュメントから:

コレクション フレームワークは、コレクションを表現および操作するための統一されたアーキテクチャであり、表現の詳細とは無関係にコレクションを操作できます。パフォーマンスを向上させながら、プログラミングの労力を軽減します。無関係な API 間の相互運用性を可能にし、新しい API の設計と学習の労力を軽減し、ソフトウェアの再利用を促進します。

補遺

以下のコメントのほとんどは、これは単なる演習であり、プログラマーのスキルを判断するためのものであると主張しています。これに対する私の反論は単純です。

この「インタビュー」は、Java プログラミングのポジションを対象としています。オブジェクト指向言語である Java には、(C や他のさまざまな低レベル言語のように) プロセスをゼロから設計する必要なく、このようなタスクを実行する機能があります。さらに、スペースの複雑さが懸念される場合、Java は最適な選択ではありません。そうは言っても、上記のリストのエントリ 1 をもう一度読んでください。

于 2012-05-26T15:30:21.150 に答える
4

ウィキペディアで定義されている線形ハッシュには、サイズ変更が段階的に行われるという利点があります。これは、バケットがラウンドロビン方式で 1 ​​つずつ分割され、サイズ変更による挿入の償却時間の複雑さが一定に保たれるためです。したがって、彼らのアイデアは、線形ハッシュのストレージとして既に反復された要素を再利用して、配列を反復処理することです。

私は線形ハッシュの専門家ではありませんが、ハッシュ テーブルを配列に収める方法がわかりません。確かに、線形ハッシングで n 個の要素を保存するには、n 個のバケットを使用するだけで十分です。ただし、バケット内の要素の数は無制限であるため、各バケットを実装するには、リンクされたリストのようなものが必要になり、ポインター用に追加の O(n) メモリが必要になります。

そのため、このアルゴリズムは、通常の よりも優れた漸近空間複雑度を生成しませんHashSet。ただし、一定の係数でメモリ消費を削減します。

その時間計算量は、通常の と同等HashSetです。

編集：この回答は無視されているようです（投票もコメントもありません）。役に立ちませんか？コメントしてください。改善すべき点がわかりました。

于 2012-05-26T16:06:07.793 に答える
4

1 つのアイデアがあります。配列を下に進むにつれて、アクセスした部分を並べ替えます。二分探索を採用することで、時間を短縮できます。スペースは0です。ソート自体は...挿入ソートですか？基本的には普通に並べ替えを行っているのですが、新しい数字を挿入する場所を探す際に、数字自体にヒットすると「ビンゴ」と叫びます。これは、ゼロ スペース + O(n 2 ) 時間よりも改善されています。

于 2012-05-26T15:13:57.407 に答える
2

まあ、あなたは自分で答えを出します.線形ハッシュは存在します. http://cgi.di.uoa.gr/~ad/MDE515/e_ds_linearhashing.pdfによると、複雑さ o(1)/o(1) が あるため、使用中に配列から要素を次々に取り出します最初のいくつかはハッシュ マップのメモリとして使用されます。
しかし実際には、それは自分で実装するデータ構造です。

「他のデータ構造なしで」それを解決する必要があるとインタビューが言わなかったか、インタビュアーが実際にデータ構造を自分で実装したとしてもデータ構造であることを理解していなかったかのいずれかです。

とにかく、主に、それはあなたが知っているか知らないかのどちらかの種類の質問だからです. 面接中にこれを思いつく方法はありません。あなたが彼らのために働かないことを願っています。

于 2012-05-26T15:28:39.327 に答える
2

これは線形ハッシュを使用しませんが、O(N 2 )よりも高速に動作します。

  1. いくつかの小さな数値 C を選択し、ブルート フォース アルゴリズムを使用して、配列の最初の C 要素の最初の重複を見つけます。まだ何も見つからない場合は、最初の C 要素をクリアします。
  2. 最初の N 要素を空にして、残りの手順を実行します。最初は、N=C です。各反復の後、N は 2 倍になります。
  3. インデックス N+1 .. 3*N/2 の数値をハッシュ テーブルの最初の N 配列要素に順次追加します。オープン アドレッシングを使用します。N/2 個の要素がすべて移動された後、ハッシュの負荷係数は 1/2 になります。移動したばかりの N/2 要素で占められている空きスペース。次の N/4 要素については、これまでに作成されたハッシュ テーブルでそれぞれを検索し、常に要素数の 2 倍のスペースにハッシュします。NC 配列要素がハッシュされるまでこれを続けます。ハッシュ テーブル内の残りの C 要素を検索し、それらを互いに比較します。
  4. これで、重複のない N 個の配列要素があり、2*N のスペースを占めています。それらをその場で再ハッシュします。
  5. このハッシュ テーブル内の配列の他のすべての要素を順次検索します。次に、これらの 2*N 要素をクリアし、N=2*N に設定して、手順 3 に進みます。

手順 3..5 は簡略化できます。要素 N+1 .. 3*N/2 をハッシュし、このハッシュ テーブルで配列の他のすべての要素を検索します。次に、要素 3*N/2+1 .. 2*N について同じことを行います。これは元のアルゴリズムの 2 倍遅くなりますが、それでも平均で O(N log N) です。

別の方法として、最初の N 個の空の要素を使用して、要素 N+1 .. 3*N/2 のバイナリ検索ツリーを構築し、このツリー内の配列の他のすべての要素を検索する方法があります。次に、要素 3*N/2+1 .. 2*N について同じことを行います。(これは、配列が十分に小さく、その要素が整数値でインデックス付けされている場合にのみ機能します)。

上記のアルゴリズムは確率論的であり、平均して O(N log N) 時間で機能します。最悪の場合の複雑さは O(N 2 ) です。バイナリ検索ツリーを使用した代替案は、ツリーが自己均衡している場合、最悪の場合の複雑さが O(N log 2 N) になる可能性があります。しかし、これは複雑です。より単純なアルゴリズムを使用すると、O(N log 2 N) の最悪の場合の時間でタスクを実行できます。

このアルゴリズムは、配列を順次反復し、次の不変条件を維持します。サイズが 2 のべき乗で、現在の位置の左側に収まる可能な最大のサブ配列で、インデックス 0 から始まり、並べ替えられます。次にそのようなサブ配列が続き、これもソートされます。言い換えると、現在のインデックスのバイナリ表現は、ソートされたサブ配列がその前にいくつあるかを示します。たとえば、インデックス 87 (1010111) の場合、インデックス 86 に単一の要素、インデックス 84 に並べ替えられたペア、80 に 4 要素の並べ替えられたサブ配列、64 に 16 要素の並べ替えられたサブ配列、および並べ替えられたペアがあります。配列の先頭にある 64 要素のサブ配列。

  1. 配列を反復処理する
  2. 二分探索を使用して、先行するすべてのサブ配列で現在の要素を検索します。
  3. 現在の要素を、現在のインデックスのバイナリ表現の末尾の「1」に対応する先行するサブ配列と一緒に並べ替えます。たとえば、インデックス 87 (1010111) の場合、現在の要素を 3 つのサブ配列 (1+1+2+4=8 要素) と共に並べ替える必要があります。このステップにより、アルゴリズムの不変を維持しながら、現在の要素をサブ配列に追加できます。
  4. ステップ 1 の次の繰り返しに進みます。
于 2012-05-26T17:12:24.963 に答える
0

これには、追加のメモリはなく、レジスタのみという追加の制限が提示されました。これが私が思いついたものです：

outer: for (i = 0; i < arr.length - 1; i++)
 for (j = i+1; j < arr.length; j++)
   if (arr[i] == arr[j])
     break outer;

i と j が < arr.length の場合、これらは最初の重複値のインデックスであり、一致します。

j が arr の全長をカバーすることはないため、O(n^2) よりも少しだけ優れています。

于 2012-05-26T15:29:43.727 に答える
0

これが O(n) Time on a Average アルゴリズムです

public static int firstRepeatingElement(int[] elements) {
    int index = -1;
    Set<Integer> set = new HashSet<Integer>();

    for (int i = elements.length - 1; i >=0; i--) {
        if (set.contains(elements[i])) {
            index = i;
        }
        set.add(elements[i]);
    }
    if (index != -1) {
        return elements[index];
    }
    throw new IllegalArgumentException("No repeating elements found");
}

ここにテストケースがあります

@Test
public void firstRepeatingElementTest() {
    int [] elements = {1,2,5,7,5,3,10,2};
    int element = ArrayUtils.firstRepeatingElement(elements);
    assertThat(element, is(2));
}

@Test(expected=IllegalArgumentException.class)
public void firstRepeatingElementTestWithException() {
    int [] elements = {1,2,5,7,3,10};
    int element = ArrayUtils.firstRepeatingElement(elements);
    assertThat(element, is(2));
}
于 2016-02-23T18:01:02.763 に答える
0

擬似コード:

res = -1;
startArray = [...];
sortedArray = mergeSort(startArray);
for i = 1 to n
     x = bynary_search(sortedArray, startArray[i]); //array, element
     if ((sorted_array[x] == sortedArray[x-1])    ||   (sorted_array[x] == sortedArray[x+1]))
           res = i;
           break;
if (res != -1)
     print('First duplicate is ',startArray[res]);
else
     print('There are no duplicates');

最悪の場合のマージソート O(n log n)

二分探索ワーストケース O(log n)

n 回 二分探索ワーストケース O(n log n)

合計 O(n log n)

于 2012-05-28T08:31:21.923 に答える
0

これが、インタビュアーが求めていた「線形ハッシュ」ソリューションだと思います。最初に、2 つの追加の制約を想定する必要があります。

  1. A の長さ >= A の最大値
  2. A の値はすべて正です

これらの追加の制約により、より少ない時間とスペースで問題を解決できます。

では、コードに取り掛かりましょう。

int findFirstDuplicateEntry(int[] A) {
    for (int i=0; i<A.length; i++) {
        if (A[Math.abs(A[i])-1]<0)
            return Math.abs(A[i]);
        else {
            A[Math.abs(A[i])-1] = -A[Math.abs(A[i])-1];
        }
    }
    return -1;
}

ここで行っているのは、配列自体を使用して追加情報を格納することです。配列を反復処理するとき、値に遭遇するたびに、その値をindexとして使用します。このインデックスで値を確認します。値が負の場合、私は以前にここにいたことを知っています (すべて正の制約のため)。したがって、最初の複製を見つけたので、終了できます。それ以外の場合は、そのインデックスの値を否定します。

于 2018-05-17T15:21:24.910 に答える