事前に並べ替えられた複数の可変サイズの文字列配列があり、各配列に含まれるすべての要素を見つける必要があります。たとえば、配列がある場合
{"cat", "dog", "horse"},
{"dog", "donkey", "horse"},
{"cat", "dog", "donkey", "horse"}
結果配列を
{"dog", "horse"}
これを達成するための効果的な方法は何ですか?
これはどう...
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;
}
}
配列が昇順でソートされていると仮定してアルゴリズムを説明します
3 つの配列のそれぞれにインデックスを作成し、0 に設定します。
配列のインデックスで最小の要素を特定し、その配列のインデックスをインクリメントします。
最小の要素が 2 つの配列の先頭にある場合は、重複が見つかりました。
両方(すべて)のインデックスをインクリメントできます。
このアルゴリズムはO(n)時間かかるはずです。
配列が同じ要素を 2 つ持つことができる場合とできない場合があります。可能であれば、配列の前の要素を追跡し、それを現在の要素と比較して、そのような重複を見つける必要があるかもしれません。
セットの交差点に関する解決策が好きですが、次のことも提案したいと思います。
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");
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
複数の配列を独自の配列、つまり多次元配列に保持することは間違いありません。あなたができることは、2番目の配列を持ち、マルチ配列をループすることです...可能なすべての要素をこの新しい配列に入れます...つまり、{猫、犬、馬、ロバ}
これが完了すると、配列を循環して、すべての要素を含む「マスター配列」と比較できます。マスター配列にある要素が配列に含まれていない場合は、その要素をマスターから削除します。最後に、マスター配列には、元の配列のすべてにあるすべての要素が含まれます。もっとエレガントな解決策があるかもしれないことは認めます...しかし、これはうまくいきます!
Arrays.asList(...).contains(...)
. これにより、配列をリストに変換し、配列を繰り返し処理することなく、配列に要素が含まれているかどうかを簡単に確認できます。存在する場合は、他の配列を引き続きチェックして、それがすべての配列で共通の要素であるかどうかを確認します。
配列を に配置し、各 Set でjava.util.Set
メソッドを呼び出すだけです。contains
(フェset.contains("horse")
); 同じ文字列が含まれている場合は を返しtrue
、そうでない場合false
はすべての結果を確認します。