w****o
发帖数: 2260 | 1 求两个数组的union 和intersection的时候，
如果数组里面有重复的数，在怎么处理？
比如 a[] = {3 2 5 7 8 5 6 5 9} //有三个5
b[]= {11 9 5 4 3 5} //有两个5
1. 最简单的方法，从a里取每个数a[i]，然后在b里做sequential search,看a[i]是否
在b里，这样的话，交集里面就会有三个5，
可是如果取b里的数，到a里面去找的，交集里会有两个5.
到底结果里应该有几个5?
同样并集里，有三个5还是两个5?
2. 如果先把a, b排序，然后用binary search的方法，也是有方法一里面的问题
3. 如果先把a, b排序，然后用两个指针，遍历两个数组，如果遇到两个数相同的话，
把两个指针都向前移动一步，这样的话可以避免上面的问题。
大家说说这个简单的问题该如何解决？
谢谢！ | p*****2
发帖数: 21240 | 2 Hashtable也行
求两个数组的union 和intersection的时候，如果数组里面有重复的数，在怎么处理？
比如 a[] = {3 2 5 7 8 5 6 5 9}
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
【在 w****o 的大作中提到】
: 求两个数组的union 和intersection的时候，
: 如果数组里面有重复的数，在怎么处理？
: 比如 a[] = {3 2 5 7 8 5 6 5 9} //有三个5
: b[]= {11 9 5 4 3 5} //有两个5
: 1. 最简单的方法，从a里取每个数a[i]，然后在b里做sequential search,看a[i]是否
: 在b里，这样的话，交集里面就会有三个5，
: 可是如果取b里的数，到a里面去找的，交集里会有两个5.
: 到底结果里应该有几个5?
: 同样并集里，有三个5还是两个5?
: 2. 如果先把a, b排序，然后用binary search的方法，也是有方法一里面的问题
| w****x
发帖数: 2483 | 3 这个不就是merge sort吗, 先排序, 后merge, 如果有相同的就两个游标同时++ | K*****k
发帖数: 430 | | w****o
发帖数: 2260 | 5 你的这个方法，适合求并集， 复杂度是 m log m + n log n + m + n
可是你的方法，如何求交集？没有弄明白。
另外我觉得你的方法求并集的复杂度太高了。如果只把短的数组排序，用binary
search到短的数组中查找长数组里的数，这样的复杂度是 m log m + n log m (假设
m < n), 不过这个方法正像我在原帖里说的，没有办法处理重复的情形。
【在 w****x 的大作中提到】
: 这个不就是merge sort吗, 先排序, 后merge, 如果有相同的就两个游标同时++
| w****x
发帖数: 2483 | 6
设
这种merge的方法可以处理并集和交集吧. 而且可以处理重复情况
主要是编程简单.
对了, 你说的方法的确是一种优化, 可以通过分配一个和m一样大的数组来做记录, 记
录对应的index是否被访问过, 需要一种改进的binary search方法, 同时检查排序的小
数组和index 记录数组
【在 w****o 的大作中提到】
: 你的这个方法，适合求并集， 复杂度是 m log m + n log n + m + n
: 可是你的方法，如何求交集？没有弄明白。
: 另外我觉得你的方法求并集的复杂度太高了。如果只把短的数组排序，用binary
: search到短的数组中查找长数组里的数，这样的复杂度是 m log m + n log m (假设
: m < n), 不过这个方法正像我在原帖里说的，没有办法处理重复的情形。
|
|
