在Java中查找两个数组列表中共同元素的索引

Question

我有几个没有重复元素的ArrayList。我想找到它们的交集，并返回每个ArrayList中共同元素的索引。
例如，如果我的输入为{0,1,2},{3,0,4},{5,6,0}，那么我想返回{0},{1},{2}，即这里共同元素0的索引。
我能想到的一种方法是在所有ArrayList上连续使用retainAll()来获取交集，然后使用indexOf()为每个输入ArrayList找到交集元素的索引。
是否有更好的方法来实现？

- Happy Mittal

---

你是否期望你的列表中只有一个元素是共同的？ - gipsy

不，可能有很多。 - Happy Mittal

“更好”是指“更优雅”还是“更高效”？我怀疑每个问题都会得到不同的答案。 - sprinter

Answer 1

首先对列表进行排序至少需要 O(nlogn) 的时间。如果你正在寻找更有效率的算法，可以使用哈希表来达到 O(n)。

例如，使用

A=[0,1,2],B=[3,0,4],C=[5,6,0]

你可以循环遍历每个列表，并在元素上附加一个哈希。最终的哈希将会是：

H = {0:[0,1,2], 1:[1], 2:[2], 3:[0], 4:[2], 5:[0], 6:[1]}

这里，关键是元素，值是对应列表中的索引。现在，只需循环遍历哈希表以查找大小为3的任何列表，以获取其索引。

---

代码大致如下（未经测试）：

int[][] lists = {{0,1,2}, {3,0,4}, {5,6,0}};

// Create the hashmap
Map<Integer, List<Integer>> H = new HashMap<Integer, List<Integer>>();
for(int i = 0; i < lists.length; i++){
    for(int j = 0; j < lists[0].length; j++){
        // create the list if this is the first occurance
        if(!H.containsKey(lists[i][j]))
            H.put(lists[i][j], new ArrayList<Integer>());

        // add the index to the list
        H.get(lists[i][j]).add(j);
    }
}

// Print out indexes for elements that are shared between all lists
for(Map.Entry<Integer, List<Integer>> e : H.entrySet()){
    // check that the list of indexes matches the # of lists
    if(e.getValue().size() == lists.length){
        System.out.println(e.getKey() + ":" + e.getValue());
    }
}

编辑：我刚注意到你在问题中建议使用retainAll()。这也是O(n)。

- bcorso

Answer 2

这里有一个非常低效但相当易读的解决方案，使用流返回一个列表的列表。

int source[][];

Arrays.stream(source)
    .map(list -> IntMap.range(0, list.length)
        .filter(i -> Arrays.stream(source)
            .allMatch(l -> Arrays.binarySearch(l, list[i]) >= 0))
        .collect(Collectors.toList()))
    .collect(Collectors.toList());

如果需要，您可以添加toArray调用以转换为数组。

- sprinter