M*******n
发帖数: 66 | 1 使用HashSet去寻找多个lists的common elements,要求不能用HashSet的retailAll
method.
For example, consider the following collection of lists of integers:
A1=[ 3 4 9 8 12 15 7 13]
A2=[ 15 24 50 12 3 9 ]
A3=[ 78 65 24 13 9 3 12]
A4=[ 15 78 14 3 2 9 44 12 ]
Then the common elements in this collection would be: [ 3 9 12]
实在不知道，这个题目的基本思路是什么？
求帮助！ |
n******7
发帖数: 12463 | 2 实现一下retainAll就好了
382 public boolean retainAll(Collection c) {
383 boolean modified = false;
384 Iterator e = iterator();
385 while (e.hasNext()) {
386 if (!c.contains(e.next())) {
387 e.remove();
388 modified = true;
389 }
390 }
391 return modified;
392 } |
h*****0
发帖数: 4889 | 3 最笨的n^2算法：
先用一个hash set记下所有的元素。
再依次遍历每一个list
遍历list a时，建一个hash set sa，遍历hash set并将其中不属于sa的元素移除。
lists
【在 M*******n 的大作中提到】
: 使用HashSet去寻找多个lists的common elements,要求不能用HashSet的retailAll
: method.
: For example, consider the following collection of lists of integers:
: A1=[ 3 4 9 8 12 15 7 13]
: A2=[ 15 24 50 12 3 9 ]
: A3=[ 78 65 24 13 9 3 12]
: A4=[ 15 78 14 3 2 9 44 12 ]
: Then the common elements in this collection would be: [ 3 9 12]
: 实在不知道，这个题目的基本思路是什么？
: 求帮助！
|
h*****0
发帖数: 4889 | 4 这个应该是O(n*K)，n为总数，K为list的数目
【在 h*****0 的大作中提到】
: 最笨的n^2算法：
: 先用一个hash set记下所有的元素。
: 再依次遍历每一个list
: 遍历list a时，建一个hash set sa，遍历hash set并将其中不属于sa的元素移除。
:
: lists
|
h*****0
发帖数: 4889 | 5 很显然，记下所有元素是没必要的。最初的hash set只需要记下第一个list的元素。然
后同法遍历其它list
O(n)
all
retailAll
【在 h*****0 的大作中提到】
: 这个应该是O(n*K)，n为总数，K为list的数目
|
M*******n
发帖数: 66 | 6 多谢！我就是用你提供的思路解决这个问题。
【在 h*****0 的大作中提到】
: 很显然，记下所有元素是没必要的。最初的hash set只需要记下第一个list的元素。然
: 后同法遍历其它list
: O(n)
:
: all
: retailAll
|
M*******n
发帖数: 66 | 7 多谢 source code!
【在 n******7 的大作中提到】
: 实现一下retainAll就好了
: 382 public boolean retainAll(Collection c) {
: 383 boolean modified = false;
: 384 Iterator e = iterator();
: 385 while (e.hasNext()) {
: 386 if (!c.contains(e.next())) {
: 387 e.remove();
: 388 modified = true;
: 389 }
: 390 }
|
h**********c
发帖数: 4120 | 8 这个不是集合论吗
A ^ B = A - ( A - B)
- removeall |
g*********e
发帖数: 14401 | 9 这个不就是所有数字扫一遍吗？还是我miss了什么
【在 M*******n 的大作中提到】
: 使用HashSet去寻找多个lists的common elements,要求不能用HashSet的retailAll
: method.
: For example, consider the following collection of lists of integers:
: A1=[ 3 4 9 8 12 15 7 13]
: A2=[ 15 24 50 12 3 9 ]
: A3=[ 78 65 24 13 9 3 12]
: A4=[ 15 78 14 3 2 9 44 12 ]
: Then the common elements in this collection would be: [ 3 9 12]
: 实在不知道，这个题目的基本思路是什么？
: 求帮助！
|
