2

我有一个List<Integer>，这个列表包含重复的元素：

//myList content is something like e.g. 1,2,1,3,3,6,7,...
List<Integer> myList = getNumbers();

Set<String>众所周知，我还有一个，Set只包含独特的元素，没有重复的元素。我的Set<String>包含字符串类型整数：

//The Set content is String type integer , e.g. "1", "3", "5" …
Set<String> mySet = getNumSet();

我想比较mySet找出myList哪些元素mySet有但myList没有并从中删除这些元素mySet。

我现在的方法是使用嵌套迭代，如下所示：

for(Integer i : myList){
   for(String s : mySet){
         if(!myList.contains(Integer.valueOf(s))){
               mySet.remove(s);
         }
    }   

}

有比我更有效的方法吗？

4

4 回答 4

2 
    for (Iterator<String> it = mySet.iterator(); it.hasNext();) {
        if(myList.contains(Integer.parseInt(it.next()))){
            it.remove();
        }
    }
于 2013-11-05T09:30:37.980 回答
2

最简单的方法可能是使用Collection#retainAll(Collection<?> c)它可以通过对集合类型的功能进行一些优化来实现。

mySet.retainAll(myList)

但是mySetandmyList必须是Set<X>and List<X>。我建议您更改声明mySet并用类似的内容填充它Integer#valueOf(String s)，然后使用该retainAll方法。

于 2013-11-05T09:25:22.643 回答
1
  1. 复制集合。
  2. 遍历列表，从副本中删除找到的项目。
  3. 从原始集合中减去副本。

假设集合中有m个元素，列表中有n 个元素。

然后从集合中删除项目是O(log m)并且遍历列表是O(n)。总体复杂度为O(n × log m)。减法最多为O(m × log m)，因此整体复杂度为O(s × log s)其中s = max(m, n)。

你的算法的复杂度是O(n 2 × (log m) 2 )，因为你

  1. 遍历列表（O(n)）并为每个项目
  2. 遍历集合（O(log m)），
  3. 在列表中找到对应的项目（O(n)），最后
  4. 如果合适（ O(log m) ）将其从集合中删除。
于 2013-11-05T09:24:36.433 回答
0

实际上，需要更多信息才能找到最佳方法。

如果 myList.size() >> mySet.size()，遵循 Oswald 的解决方案，或者

  1. 创建一个新的字符串集。
  2. 对于 myList 中的每个项目，如果它不在 mySet 中，则将其保存到 newSet。
  3. 调用 mySet.removeAll(newSet)。

如果 mySet.size() >> myList.size()，最好的解决方案是将 myList 转换为新的 String 集，然后调用 mySet.retainAll 方法。

于 2013-11-05T21:20:06.943 回答