java - 在java中的arraylists中查找公共(public)元素的索引

Question

我有几个没有重复元素的 ArrayList。我想在每个数组列表中找到它们的交集并返回公共(public)元素的索引。
例如，如果我输入的是 {0,1,2},{3,0,4},{5,6,0}，那么我想返回 {0} ,{1},{2} 即此处公共(public)元素 0 的索引。
我能想到的一种方法是在所有 ArrayList 上使用连续的 retainAll() 来获得交集，然后使用 indexOf() 为每个输入 ArrayList 找到交集元素的索引.
有更好的方法吗？

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]}

这里，键是元素，值是它在对应列表中的索引。现在，只需遍历 hashmap 以找到大小为 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)。