64,656
社区成员
发帖
与我相关
我的任务
分享一道vector效率题
vector<int> v1,v2,v3,
v1,v2里是不重复的数据，现要找出v1,v2中重复的数据保存到v3中。
考虑v1,v2,有大量数据时，怎样提高效率。
v1,v2里是不重复的数据，现要找出v1,v2中重复的数据保存到v3中。
考虑v1,v2,有大量数据时，怎样提高效率。
...全文
请发表友善的回复…
发表回复
chenxu_ustc 2009-05-15
- 打赏
- 举报
[Quote=引用 8 楼 goodname 的回复:]
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));
[/Quote]
beautiful
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));
[/Quote]
beautiful
liao05050075 2009-05-15
- 打赏
- 举报
关键在于你的v1,v2里面最大的元素是多大？
xf_pan 2009-05-15
- 打赏
- 举报
用hash，对于这题，具体应该怎么做呢。
ShardowM 2009-05-15
- 打赏
- 举报
学习
jiangfeng999 2009-05-15
- 打赏
- 举报
先排序,然后v1,v2再从头到尾进行查找,这样可以省去很多重复遍历的次数
排序函数
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
排序函数
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
beyond071 2009-05-15
- 打赏
- 举报
解决的挺好 学习了
insulted 2009-05-15
- 打赏
- 举报
我来学习。。。。
amossavez 2009-05-15
- 打赏
- 举报
先排序，用stl提供的排序算法sort，再求两个vector的交集，hash不见得比这个好，在你不了解hash的情况之下！！
liao05050075 2009-05-15
- 打赏
- 举报
[Quote=引用 32 楼 xf_pan 的回复:]
引用 31 楼 hejinjing_tom_com 的回复:
自己写set, 用c 写， 当你创建完set, 重复值也就全找好了。
就是说建立一个红黑树，把v1,v2 数据全存进去，发现重复放到v3 中去。
缺点就是自己写。累点，但效率高。
同意楼上
也认为此题在这里考察的就是这种方法，
题意有，v1,v2,本身没有重复数据，新建一个空set，用v1,v2,size大的去初始化这个set（假如v2 size大）,然后遍历
插入v1,找到重复的，，
[/Quote]
事实上，用红黑树与排序再STL求交没什么实质性区别，算法的复杂度都是O（nlogn）
引用 31 楼 hejinjing_tom_com 的回复:
自己写set, 用c 写， 当你创建完set, 重复值也就全找好了。
就是说建立一个红黑树，把v1,v2 数据全存进去，发现重复放到v3 中去。
缺点就是自己写。累点，但效率高。
同意楼上
也认为此题在这里考察的就是这种方法，
题意有，v1,v2,本身没有重复数据，新建一个空set，用v1,v2,size大的去初始化这个set（假如v2 size大）,然后遍历
插入v1,找到重复的，，
[/Quote]
事实上，用红黑树与排序再STL求交没什么实质性区别，算法的复杂度都是O（nlogn）
hai040 2009-05-15
- 打赏
- 举报
[Quote=引用 28 楼 xf_pan 的回复:]
用hash，对于这题，具体应该怎么做呢。
[/Quote]
直接用boost的hash_set
用hash，对于这题，具体应该怎么做呢。
[/Quote]
直接用boost的hash_set
xf_pan 2009-05-15
- 打赏
- 举报
[Quote=引用 31 楼 hejinjing_tom_com 的回复:]
自己写set, 用c 写， 当你创建完set, 重复值也就全找好了。
就是说建立一个红黑树，把v1,v2 数据全存进去，发现重复放到v3 中去。
缺点就是自己写。累点，但效率高。
[/Quote]
同意楼上
也认为此题在这里考察的就是这种方法，
题意有，v1,v2,本身没有重复数据，新建一个空set，用v1,v2,size大的去初始化这个set（假如v2 size大）,然后遍历
插入v1,找到重复的，，
自己写set, 用c 写， 当你创建完set, 重复值也就全找好了。
就是说建立一个红黑树，把v1,v2 数据全存进去，发现重复放到v3 中去。
缺点就是自己写。累点，但效率高。
[/Quote]
同意楼上
也认为此题在这里考察的就是这种方法，
题意有，v1,v2,本身没有重复数据，新建一个空set，用v1,v2,size大的去初始化这个set（假如v2 size大）,然后遍历
插入v1,找到重复的，，
hjjdebug 2009-05-15
- 打赏
- 举报
自己写set, 用c 写， 当你创建完set, 重复值也就全找好了。
就是说建立一个红黑树，把v1,v2 数据全存进去，发现重复放到v3 中去。
缺点就是自己写。累点，但效率高。
就是说建立一个红黑树，把v1,v2 数据全存进去，发现重复放到v3 中去。
缺点就是自己写。累点，但效率高。
hityct1 2009-05-15
- 打赏
- 举报
设两个vector长度：m\n
1）分别排序。 时间复杂度： O(mlogm)+O(nlogn)
2）然后用两个迭代器分别指向两个vector头部，然后比较两个迭代器指向的元素的大小，小的就向后移，然后再比较，如果有相等的就写入第三个vector。 时间复杂度：O(m+n)
1）分别排序。 时间复杂度： O(mlogm)+O(nlogn)
2）然后用两个迭代器分别指向两个vector头部，然后比较两个迭代器指向的元素的大小，小的就向后移，然后再比较，如果有相等的就写入第三个vector。 时间复杂度：O(m+n)
Qlaiaqu 2009-05-14
- 打赏
- 举报
排序后找重复吧，连标准模板库中的某个函数都是这么实现的，不记得名字了
iambic 2009-05-14
- 打赏
- 举报
很多时候有序是自然而然的，不需要或者只需要简单的维护。
Hash虽然很多时候很快，用来求交集却很容易效率低下。
Hash虽然很多时候很快，用来求交集却很容易效率低下。
linfengc 2009-05-14
- 打赏
- 举报
hash
liao05050075 2009-05-14
- 打赏
- 举报
[Quote=引用 16 楼 iambic 的回复:]
先排序，然后求交集。
hash很慢的。
[/Quote]
Hash的复杂度是O(n)的，
排序的复杂度是O(nlogn)的，加上STL的求交是O(n)
这个不挺明显的吗？
先排序，然后求交集。
hash很慢的。
[/Quote]
Hash的复杂度是O(n)的，
排序的复杂度是O(nlogn)的，加上STL的求交是O(n)
这个不挺明显的吗？
zhaohongbo83 2009-05-14
- 打赏
- 举报
对取交集是个不错的方法！
iambic 2009-05-14
- 打赏
- 举报
先排序，然后求交集。
hash很慢的。
hash很慢的。
kiffa 2009-05-14
- 打赏
- 举报
单论时间效率，从算法角度讲自然hash好。如果vector元素的最大值不是特别大（比如2000万以内）bitset<MAX_ELEMENT_VALUE> bitmap 还是可以用用的；
但结合现实来讲，对一个数组a的元素a[n]的随机访问虽然是常数时间，但这个常数时间并非固定不变，考虑到n的无序性，比如一个读取序列：a[1], a[1000000], a[1000]。。。如果像这种跳跃度很大的序列，必然会导致很高的cache miss率，以及可能的频繁换页，这往往导致时间效率非常低下。虽然这纯粹是次要复杂度，和问题本身的求解并没有也不应该有直接关系，但我们生活在不完美的现实世界，只能无奈的去接受它。
所以我们要先分析n的大概变化规律，没办法的话只能采取强制cache(锁页）、分块计算等纯属被逼出来的手段去对付它。
但结合现实来讲，对一个数组a的元素a[n]的随机访问虽然是常数时间，但这个常数时间并非固定不变，考虑到n的无序性，比如一个读取序列：a[1], a[1000000], a[1000]。。。如果像这种跳跃度很大的序列，必然会导致很高的cache miss率，以及可能的频繁换页，这往往导致时间效率非常低下。虽然这纯粹是次要复杂度，和问题本身的求解并没有也不应该有直接关系，但我们生活在不完美的现实世界，只能无奈的去接受它。
所以我们要先分析n的大概变化规律，没办法的话只能采取强制cache(锁页）、分块计算等纯属被逼出来的手段去对付它。
加载更多回复（14）
