0

我有多个预先排序的可变大小字符串数组，我需要找到每个数组中包含的所有元素。例如，如果我有数组

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

我希望结果数组是

{"dog", "horse"}

什么是实现这一目标的有效方法？

4

9 回答 9

1

我将描述一个假设数组按升序排序的算法

为 3 个数组中的每一个创建一个索引，并将其设置为 0。

确定数组索引处的哪个元素最小，并增加该数组的索引。

如果最小元素位于两个数组的开头，则您找到了重复项。

您可以增加它们的两个（全部）索引。

这个算法应该花费O(n)时间。

数组可能有也可能不可能有两个相同的元素。如果可能，您可能必须跟踪数组的前一个元素并将其与当前元素进行比较以找到那些重复项。

于 2013-10-17T19:25:04.490 回答
1

给定三个数组

String[] arr1 = {"cat", "dog", "horse"};
String[] arr1 = {"dog", "donkey", "horse"};
String[] arr1 =  {"cat", "dog", "donkey", "horse"};

通过逐个迭代元素或遵循以下方法从它们创建三个Set

Set<String> set1 = new HashSet(Arrays.asList(arr1));
Set<String> set2 = new HashSet(Arrays.asList(arr2));
Set<String> set3 = new HashSet(Arrays.asList(arr3));

现在通过调用 set 接口中给出的retainAll函数来执行 set 交集

/* set1 intersection set2: results in set1 having only common elements */
set1.retainAll(set2);
/* Finally intersection of previous result and set3: final result in set1 */
set1.retainAll(set3);

有关java 集合中支持的Set操作的更多信息，请参阅此处

于 2013-10-17T19:32:40.537 回答
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 回答
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

您肯定希望将多个数组保存在自己的数组中，即：多维数组。然后你可以做的是有第二个数组并循环遍历你的多数组.....将每个可能的元素放入这个新数组中......即：{cat, dog, horse, donkey}

完成此操作后，您可以循环浏览数组并将它们与包含所有元素的“主数组”进行比较。如果数组不包含主数组中的元素，则从主数组中删除该元素。最后，主数组将包含每个原始数组中的所有元素。我承认可能有一个更优雅的解决方案......但这会奏效！

于 2013-10-17T19:28:03.607 回答
0

我将首先获取最大数组的长度并将一个新的结果数组初始化为该长度。然后使用嵌套循环比较每个已创建的字符串数组中的元素，例如比较元素'cat'、'dog'、cat。因为它们不相等，所以在最里面的数组中上移一位，比较'cat'、'dog'、'dog'等。如果元素的值在所有数组中都相等，则将该元素添加到结果数组中.

从那里你应该能够编写一个有效的解决方案。

于 2013-10-17T19:31:29.077 回答
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 回答
-1

Arrays.asList(...).contains(...). 这允许您将数组转换为列表，并且只需查看数组是否包含元素，而无需遍历它。如果是，请继续检查其他数组以查看它是否是所有数组的公共元素。

于 2013-10-17T19:26:28.843 回答
-2

你可以把你的数组放到, 并且只是在每个 Set 上java.util.Set调用方法。contains(fe set.contains("horse")); 如果它包含相同的字符串，它将返回true，否则false，然后检查所有结果。

于 2013-10-17T19:25:23.697 回答