如果vector只包含不同的元素 [英] If vector contains only different elements

问题描述

这是一个检测向量是否只包含不同元素的函数


bool vector_contains_only_different_elements（const vector< int>& v）

{

for（int i = 0; i< v.size（）; i ++）

{

if（count（v.begin（ ）+ i + 1，v.end（），v [i]）> = 1）返回false;

}

返回true;

}

还有更简单的方法可以做同样的事情吗？


-

Alex Vinokur
mailto：al **** @ connect.to
http://mathforum.org/library/view/10978.html

Here is some function that detects if a vector contains only different elements

bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?

--
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html

推荐答案

" Alex Vinokur" <人**** @ big.foot.com>在消息中写道

news：c7 ********* @ news.f.de.plusline.net ...

"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c7*********@news.f.de.plusline.net...

这里有一些功能可以检测到如果一个向量只包含不同的
元素
bool vector_contains_only_different_elements（const vector< int>& v）
{
for（int i = 0; i< v.size（ ）; i ++）
{if（count（v.begin（）+ i + 1，v.end（），v [i]）> = 1）返回false;
}
返回true;
}

有更简单的方法可以做同样的事情吗？

Here is some function that detects if a vector contains only different elements
bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?

看来很简单。


但是如果你想要一个更有效的方法，要么使用已经排序的

数据结构，例如multiset，要么首先对矢量进行排序并比较

相邻元素是否相等。


bool vector_contains_only_different_elements（const vector< int>& v）

{

vector< int> tmp（v）;

sort（tmp.begin（），tmp.end（））;

for（int i = 0; i< tmp.size（ ） - 1; i ++）

{

if（tmp [i] == tmp [i + 1]）

返回false; < br $>
}

返回true;

}


（未经测试的代码）

/>
您的代码是二次时间算法的示例。需要时间

与数组大小的平方成正比。在许多情况下，这是不可接受的慢速。我的版本有时被称为线性日志时间

算法，它需要时间与n * log（n）成比例，其中n是向量的大小

，这比二次时间算法要好得多。


为什么不在非常大的矢量上尝试两种方法，看哪哪种更快。


john

That seems simple enough.

However if you want a more efficient method, either use a already sorted
data structure such as multiset, or sort your vector first and compare
adjacent elements for equality.

bool vector_contains_only_different_elements (const vector<int>& v)
{
vector<int> tmp(v);
sort(tmp.begin(), tmp.end());
for (int i = 0; i < tmp.size() - 1; i++)
{
if (tmp[i] == tmp[i + 1])
return false;
}
return true;
}

(untested code)

Your code was an example of a quadratic time algorithm. It will take time
proportional to the square of the size of the array. In many cases this is
unacceptably slow. My version is what is sometimes called a linear log time
algorithm, it will take time proportional to n * log(n), where n is the size
of the vector, that is much better than a quadratic time algorithm.

Why not try the two methods on a very large vector, see which is faster.

john

>

您的代码是二次时间算法的示例。这需要时间
与数组大小的平方成正比。在许多情况下，这是令人无法接受的缓慢。我的版本有时称为线性log
时间算法，它需要时间与n * log（n）成比例，其中n是向量的
大小，这比二次方更好时间算法。

为什么不在一个非常大的向量上尝试这两种方法，看看哪个更快。

Your code was an example of a quadratic time algorithm. It will take time
proportional to the square of the size of the array. In many cases this is
unacceptably slow. My version is what is sometimes called a linear log time algorithm, it will take time proportional to n * log(n), where n is the size of the vector, that is much better than a quadratic time algorithm.

Why not try the two methods on a very large vector, see which is faster.

只考虑我的分析适用于最坏的情况，即

时，没有任何重复的元素。如果重复的元素很常见，你的算法可以非常快（并且比我的快得多b $ b）。


john

Thinking about it my analysis only applies to the worst case, which is when
there aren''t any duplicate elements. You algorithm could be very quick (and
quicker than mine) if duplicate elements are very common.

john

" John Harrison" <乔************* @ hotmail.com>在消息新闻中写道：2g ************ @ uni-berlin.de ...

"John Harrison" <jo*************@hotmail.com> wrote in message news:2g************@uni-berlin.de...

Alex Vinokur <人**** @ big.foot.com>在消息中写道
新闻：c7 ********* @ news.f.de.plusline.net ...

"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c7*********@news.f.de.plusline.net...

这是一个检测向量是否包含的函数只有不同的

Here is some function that detects if a vector contains only different

元素

bool vector_contains_only_different_elements（const vector< int>& v）
{
for（int i = 0 ; i< v.size（）; i ++）
{if（count（v.begin（）+ i + 1，v.end（），v [i]）> = 1 ）返回false;
}
返回true;
}

有更简单的方法可以做同样的事情吗？

bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?

但是如果你想要一个更有效的方法，要么使用已经排序的数据结构，例如multiset，要么先对你的矢量进行排序并比较
相邻的元素是平等的。

That seems simple enough.

However if you want a more efficient method, either use a already sorted
data structure such as multiset, or sort your vector first and compare
adjacent elements for equality.

[snip]


使用set：

bool vector_contains_only_different_elements（const vector< int> ;& v）

{

return（set< int&g t;（v.begin（），v.end（））。size（）== v.size（））;

}

-

Alex Vinokur

mailto：al **** @ connect.to
http://mathforum.org/library/view/10978.html

[snip]

Using set:
bool vector_contains_only_different_elements (const vector<int>& v)
{
return ( set<int>(v.begin(), v.end()).size() == v.size());
}
--
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html

这篇关于如果vector只包含不同的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！