矢量问题 [英] Vector question
问题描述
大家好。
给定一个向量< int>，找出是否有一个
重复元素的最快方法是什么？结果只是真实。或假。谢谢。
Kitty
Hi, everyone.
Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.
Kitty
推荐答案
文章< 41 ********* *@rain.i-cable.com> ;,Kitty< No spam>写道：
In article <41**********@rain.i-cable.com>, Kitty <No spam> wrote:
给定一个向量< int>，找出是否有重复元素的最快方法是什么？结果只是真实。或假。谢谢。
Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.
我将构造一个空集< int>，然后遍历向量，依次处理
每个元素。如果元素已经在集合中，则停止并且
返回''true'';否则将元素插入集合并继续。
如果到达向量的末尾而没有找到任何重复项，则返回
''false''。
-
Jon Bell< jt ******* @ presby.edu> Presbyterian College
美国南卡罗来纳州克林顿物理与计算机科学系
I''d construct an empty set<int>, then walk through the vector, processing
each element in turn. If the element is in the set already, stop and
return ''true''; otherwise insert the element into the set and continue.
If you reach the end of the vector without finding any duplicates, return
''false''.
--
Jon Bell <jt*******@presby.edu> Presbyterian College
Dept. of Physics and Computer Science Clinton, South Carolina USA
" Kitty" <没有垃圾邮件>在消息新闻中写道：41 ********** @ rain.i-cable.com ......
"Kitty" <No spam> wrote in message news:41**********@rain.i-cable.com...
给定一个向量< int>，最快的是什么找出是否有
a重复元素的方法呢？结果只是真实。或假。谢谢。
Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks.
听起来像面试问题。有很多答案，每个都有
的权衡。 Jon的方法使用额外的内存，但是时间很快（时间
是N * O（lg（N），空间是O（N）），也很容易写 - 因为软件更容易编写和维护，所以很长一段时间可以获得回报，但这很少会在面试时出现（尽管应该这样）。你可以另外
不使用额外的内存，但牺牲时间（时间为O（N ^ 2），空间
为O（1））。并且每种方法都有自己的varations，例如set或hashtable，
类型的哈希函数，如果哈希，集合或排序的向量，向量或列表等，
等
Sounds like an interview question. There are many answers, each with
tradeoffs. Jon''s method uses additional memory, but is fast time wise (time
is N*O(lg(N), space is O(N)), and easy to write too -- that''s important too
because software that is easier to write and maintain pays off long term,
though this rarely comes up in interviews (though it should). You can also
not use additional memory, but sacrifice time (time would be O(N^2), space
is O(1)). And each method has its own varations, such as set or hashtable,
type of hash function if a hash, set or sorted vector, vector or list, etc,
etc.
在一个类似的问题中，我使用了一种不同的方法，因为
jon'的解决方案不是一个选项，因为它消耗了太多的memmory。 br />
我使用修改后的qsort，如果两个过度的元素相同，我会返回true。这个小列表很慢但是
快速使用庞大的数据集（在我的申请中大约需要30,000英镑）
但不需要额外的记忆！
/ Casper
Kitty写道：
In a similar problem, I use a different approach due to the fact that
jon''s solution is not an option as it consumes too much memmory.
I use a modified qsort and in the comparation part if two sucessive
elements are the same, I return true. This is slow with small lists but
fast with huge datasets (30.000+ as in my application takes about 100ms)
but require no additional memmory!
/Casper
Kitty wrote:
大家好。
给定一个向量< int>，找出是否有
重复元素吗？结果只是真实。或假。谢谢。
Kitty
Hi, everyone.
Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.
Kitty
这篇关于矢量问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
