矢量问题

扫码查看
本文介绍了矢量问题的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

大家好。


给定一个向量< 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

推荐答案




我将构造一个空集< 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





听起来像面试问题。有很多答案,每个都有

的权衡。 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.




这篇关于矢量问题的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-05 09:45
查看更多