0

事前に並べ替えられた複数の可変サイズの文字列配列があり、各配列に含まれるすべての要素を見つける必要があります。たとえば、配列がある場合

 {"cat", "dog", "horse"}, 
 {"dog", "donkey", "horse"},
 {"cat", "dog", "donkey", "horse"}

結果配列を

{"dog", "horse"}

これを達成するための効果的な方法は何ですか？

4

9 に答える 9

1

これはどう...

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class CommonElements {
    public static void main(String[] args) {
        String[] one = {"cat", "dog", "horse"};
        String[] two = {"dog", "donkey", "horse"};
        String[] three = {"cat", "dog", "donkey", "horse"};

        List<String> result = findCommonElements(one, two, three);

        for (String s : result)
            System.out.println(s);
    }

    public static List<String> findCommonElements(String[] ... args) {
        Map<String, Integer> map = new HashMap<String, Integer>();

        for (String[] strings : args) {
            for (String s : strings) {
                Integer current = map.get(s);
                map.put(s, current == null ? 1 : current + 1);
            }
        }

        List<String> result = new LinkedList<String>();
        for (Entry<String, Integer> entry : map.entrySet())
            if (entry.getValue() == args.length)
                result.add(entry.getKey());

        return result;
    }
}
于 2013-10-17T19:40:17.553 に答える
1

配列が昇順でソートされていると仮定してアルゴリズムを説明します

3 つの配列のそれぞれにインデックスを作成し、0 に設定します。

配列のインデックスで最小の要素を特定し、その配列のインデックスをインクリメントします。

最小の要素が 2 つの配列の先頭にある場合は、重複が見つかりました。

両方（すべて）のインデックスをインクリメントできます。

このアルゴリズムはO(n)時間かかるはずです。

配列が同じ要素を 2 つ持つことができる場合とできない場合があります。可能であれば、配列の前の要素を追跡し、それを現在の要素と比較して、そのような重複を見つける必要があるかもしれません。

于 2013-10-17T19:25:04.490 に答える
0

セットの交差点に関する解決策が好きですが、次のことも提案したいと思います。

final String array[][] = {
     {"cat", "dog", "horse"}, 
     {"dog", "donkey", "horse"},
     {"cat", "dog", "donkey", "horse"},
     // add more arrays here
     };

final HashMap <String, Integer> map = new HashMap<String, Integer>(array.length);
for (final String[] iArray : array)
    for (final String element: iArray)
    {
        if (map.containsKey(element))
            map.put(element, map.get(element) + 1);
        else
            map.put(element, 1);
    }

for (final String element: map.keySet())
    if (map.get(element) == array.length)
        System.out.println("keyword " + element + " exists in all arrays");
于 2013-10-17T19:36:06.037 に答える
0 
set pointers to start
while no array exhausted
  max_value = max value over pointers
  for each array
    while value at pointer < max_value
      increment pointer
      if array exhausted
        exit program
  for each array
    if value at pointer != max_value
      continue // restart from line 3
  print max_value
于 2013-10-17T19:25:46.300 に答える
0

複数の配列を独自の配列、つまり多次元配列に保持することは間違いありません。あなたができることは、2番目の配列を持ち、マルチ配列をループすることです...可能なすべての要素をこの新しい配列に入れます...つまり、{猫、犬、馬、ロバ}

これが完了すると、配列を循環して、すべての要素を含む「マスター配列」と比較できます。マスター配列にある要素が配列に含まれていない場合は、その要素をマスターから削除します。最後に、マスター配列には、元の配列のすべてにあるすべての要素が含まれます。もっとエレガントな解決策があるかもしれないことは認めます...しかし、これはうまくいきます!

于 2013-10-17T19:28:03.607 に答える
-1

Arrays.asList(...).contains(...). これにより、配列をリストに変換し、配列を繰り返し処理することなく、配列に要素が含まれているかどうかを簡単に確認できます。存在する場合は、他の配列を引き続きチェックして、それがすべての配列で共通の要素であるかどうかを確認します。

于 2013-10-17T19:26:28.843 に答える
-2

配列を に配置し、各 Set でjava.util.Setメソッドを呼び出すだけです。contains(フェset.contains("horse")); 同じ文字列が含まれている場合は を返しtrue、そうでない場合falseはすべての結果を確認します。

于 2013-10-17T19:25:23.697 に答える