7

今日のインタビューでアルゴリズムの質問がありましたが、SOメンバーの意見を取り入れたいと思います。質問は次のとおりです。

整数が昇順で等しいサイズのN配列がある場合、すべてのN配列に共通の数値をどのように選択しますか。

最初の私の考えは、最初の配列から残りの配列に至るまで要素を反復処理することでした。しかし、私が正しければ、それはN乗N回の反復になります。そこで、要素をキーとして、値をカウンターとして保持することにより、マップにカウントを追加するソリューションを思いつきました。このように、時間計算量はちょうどNだと思います。以下は私のアプローチのJavaでの実装です。

public static void main(String[] args) {

    int[] arr1 = { 1, 4, 6, 8,11,15 };
    int[] arr2 = { 3, 4, 6, 9, 10,16 };
    int[] arr3 = { 1, 4, 6, 13,15,16 };
    System.out.println(commonNumbers(arr1, arr2, arr3));
}

public static List<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3) {
    Map<Integer, Integer>countMap = new HashMap<Integer, Integer>();

    for(int element:arr1)
    {
        countMap.put(element, 1);
    }

    for(int element:arr2)
    {
        if(countMap.containsKey(element))
        {
            countMap.put(element,countMap.get(element)+1);
        }
    }

    for(int element:arr3)
    {
        if(countMap.containsKey(element))
        {
            countMap.put(element,countMap.get(element)+1);
        }
    }

    List<Integer>toReturn = new LinkedList<Integer>();

    for(int key:countMap.keySet())
    {
        int count = countMap.get(key);
        if(count==3)toReturn.add(key);
    }

    return toReturn;
}

これを3つのアレイに対して実行して、どのように機能するかを確認しました。質問はN配列について話しますが、これはまだ当てはまると思います。

私の質問は、時間計算量を念頭に置いてこの問題を解決するためのより良いアプローチはありますか？

4

9 に答える 9

9

3つのキューとして扱います。値は異なりますが、（配列インデックスをインクリメントすることによって）最小の「削除」を行います。それらが一致したら、一致を「削除」（および記録）します。

int i1 = 0;
int i2 = 0;
int i3 = 0;

while (i1 < array1.size && i2 < array2.size && i3 < array3.size) {
    int next1 = array1[i1];
    int next2 = array2[i2];
    int next3 = array3[i3];

    if (next1 == next2 && next1 == next3) {
        recordMatch(next1);
        i1++;
        i2++;
        i3++;
    }
    else if (next1 < next2 && next1 < next3) {
        i1++;
    }
    else if (next2 < next1 && next2 < next3) {
        i2++;
    }
    else {
        i3++;
    }
}

簡単にN配列に一般化できますが、Nが大きい場合は、何らかの方法で比較を最適化する必要があります（NPEの「ヒープ」）。

于 2013-03-25T15:03:49.783 に答える
5

これは、N個の配列に対する1回の並列反復と、N要素の最小ヒープで解決できると思います。ヒープでは、N個の入力配列のそれぞれから現在の要素を保持します。

アイデアは、各ステップで、要素がヒープの一番上にある（つまり最小の）配列に沿って進むというものです。

ヒープが完全に同一の値で構成されている場合は、それを検出できる必要があります。これは、ヒープに追加した最大の要素を追跡している限り、一定時間で実行できます。

各配列にM個の要素が含まれている場合、最悪の場合の時間計算量はになり、メモリO(M*N*log(N))が必要になりO(N)ます。

于 2013-03-25T15:08:29.800 に答える
2

試す

public static Set<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3) {
    Set<Integer> s1 = createSet(arr1);
    Set<Integer> s2 = createSet(arr2);
    Set<Integer> s3 = createSet(arr3);
    s1.retainAll(s2);
    s1.retainAll(s3);
    return s1;
}

private static Set<Integer> createSet(int[] arr) {
    Set<Integer> s = new HashSet<Integer>();
    for (int e : arr) {
        s.add(e);
    }
    return s;
}
于 2013-03-25T15:14:27.167 に答える
2

これが私がアルゴリズムクラスでそれを行うことを学んだ方法です。「より良い」かどうかはわかりませんが、最初にマップを作成するのではなく、配列を直接反復するため、使用するメモリとオーバーヘッドが少なくなります。

public static List<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3, ... , int[] arrN) {
    List<Integer>toReturn = new LinkedList<Integer>();

    int len = arr1.length;
    int j = 0, k = 0, ... , counterN = 0;
    for (int i = 0; i < len; i++) {
        while (arr2[j] < arr1[i] && j < len) j++;
        while (arr3[k] < arr1[i] && k < len) k++;
        ...
        while (arrN[counterN] < arr1[i] && counterN < len) counterN++;
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k] && ... && arr1[i] == arrN[counterN]) {
            toReturn.add(arr1[i]);
        }
    }

    return toReturn;
}
于 2013-03-25T15:14:28.950 に答える
2

これはO(M * N)、Mが配列の長さである場合に解決できます。

何が起こるか見てみましょうN = 2。これはソートされたリストの共通部分の問題であり、古典的なマージのようなソリューションがO(l1 + l2)時間内に実行されます。（l1 =最初の配列の長さ、l2 = 2番目の配列の長さ）。（マージアルゴリズムの詳細をご覧ください。）

ここで、帰納的問題でアルゴリズムをN回繰り返します。（たとえば、i番目の配列と前のステップの交差結果が得られます）。これにより、全体的なO(M * N)アルゴリズムが作成されます。

また、有効なアルゴリズムではすべての数値を考慮に入れる必要があるため、この最悪の場合の上限が達成可能な最善の方法であることに気付くかもしれません。したがって、より厳密な上限を持つ決定論的アルゴリズムは確立されない可能性があります。

于 2013-03-25T15:20:27.020 に答える
1

わかりました-ここでは少しナイーブかもしれませんが、手がかりは配列が昇順であるということだと思います。私のJavaはさびていますが、ここにいくつかのpseduocodeがあります。私はそれをテストしていないので、おそらく完璧ではありませんが、これを行うための高速な方法であるはずです：

I = 1
J = 1
K = 1

While I <= Array1Count and J <= Array2Count and K <= Array3Count

   If Array1(I) = Array2(J)
      If Array1(I) = Array3(K)
         === Found Match
         I++
         J++
         K++
      else
         if Array1(I) < Array3(K)
            I++
         end if
      end if
   else
      If Array1(I) < Array2(J)
         I++
      else
         if Array2(J) < Array3(K)
            J++
         else
            K++
         end if
      end if
   end if
Wend

これはオプションベース1です-オプションベース0を実行するには再コーディングする必要があります（Javaや他の言語のように）

于 2013-03-25T15:14:11.397 に答える
0

別のアプローチは、マージソートで行うのと同様のことを行うことだと思います。つまり、すべての配列を同時にウォークスルーして、同じ番号を取得します。これは、配列がソートされた順序であるという事実を利用し、出力配列以外の追加のスペースを使用しません。一般的な数字を印刷するだけでよい場合は、余分なスペースは使用されません。

public static List<Integer> commonNumbers(int[] arrA, int[] arrB, int[] arrC) {
   int[] idx = {0, 0, 0};

   while (idxA<arrA.length && idxB<arrB.length && idxC<arrC.length) {
      if ( arrA[idx[0]]==arrB[idx[1]] && arrB[idx[1]]==arrC[idx[2]] ) {
          // Same number
          System.out.print("Common number %d\n", arrA[idx[0]]);
          for (int i=0;i<3;i++)
              idx[i]++;
      } else {
          // Increase the index of the lowest number
          int idxLowest = 0; int nLowest = arrA[idx[0]];
          if (arrB[idx[1]] < nLowest) {
             idxLowest = 1;
             nLowest = arrB[idx[1]];
          }
          if (arrC[idx[2]] < nLowest) {
             idxLowest = 2;
          }
          idx[idxLowest]++;
      }
   }
}

これをより一般的にするために、intの配列の配列を取得したい場合があります。これにより、コードをよりきれいにすることができます。配列のインデックスは配列に格納する必要があります。そうしないと、「最小数を指すインデックスをインクリメントする」コードをコーディングするのが困難になります。

于 2013-03-25T15:14:21.827 に答える
0

あなたの解決策は受け入れられますが、それはNxMスペースを使用します。これは、O（N）スペース（Nは配列の数）またはO（1）スペースで実行できます。

ソリューション＃1（Luigi Mendozaによる）

小さな配列（M << N）が多数あると仮定すると、これは有用であり、O（M * N * Log M）時間、および一定のスペース（出力リストを除く）になります。

解決策＃2

配列の最新のアクセス値（およびインデックス）を含む、サイズNの最小ヒープを維持しながら、配列を昇順でスキャンします。ヒープに同じ値のコピーがN個含まれている場合は常に、その値を出力コレクションに追加します。それ以外の場合は、最小値を削除して、対応するリストに進みます。

このソリューションの時間計算量はO（M * N * Log N）です。

于 2013-03-25T15:15:09.543 に答える
0 
public static List<Integer> getCommon(List<List<Integer>> list){
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    int c=0;
    for (List<Integer> is : list) {
        c++;
        for (int i : is) {
            if(map.containsKey(i)){
                map.put(i, map.get(i)+1);
            }else{
                map.put(i, 1);
            }
        }
    }
     List<Integer>toReturn = new LinkedList<Integer>();
    for(int key:map.keySet())
    {
        int count = map.get(key);
        if(count==c)toReturn.add(key);
    }
    return toReturn;
}
于 2013-03-25T17:21:24.110 に答える