假设我们有元素的集合,这些元素只有平等的运营商。 因此,它是不可能对它们进行排序。
你怎么能挑选出那些有重复,并把它们放到各组比较的量最少? 优选在C ++,但算法比语言更重要。 对于给定的{E1,E2,E3,E4,E4,E2,E6,E4,E3}示例,我希望提取出{E2,E2},{E3,E3},{E4,E4,E4}。 你会选择什么样的数据结构和算法?
编辑
我的情况下,如果二进制数据1等于二进制数据2,我们可以说这两个元素是相同的。 但是,只有=和!=是逻辑
element 1:
4 0 obj
<< /Type /Pages /Kids 5 0 R /Count 1 >>
stream
.....binary data 1....
endstream
endobj
element 2:
5 0 obj
<< /Type /Pages /Kids 5 0 R /Count 1 >>
stream
.....binary data 2....
endstream
endobj
它足以找到任意谓词P
,使得P(a,a)==false
, P(a,b) && P(b,a)==false
, P(a,b) && P(b,c)
意味着P(a,c)
和!P(a,b) && !P(b,a)
意味着a == b
。 欠即可满足这一属性,这样则更大。 但他们从唯一的可能性是远。
您现在可以通过谓词排序您的收藏P
,哪些是相等的所有元素将是相邻的。 在你的情况,定义P(E1,E2)=true, P(E2,E3)=true
,等等。
对于你的答案,但我相信,你想这仅仅是不是100%。
如果你想好算法中试Binary search tree
的创建。 因为它是一个基团,并根据BST properties
可以方便地组元素。
例如
BST()
{
count = 0;
if(elementinserted)
count = 1;
if(newelement == already inserted element)
{
count++;
put element in array upto count value;
}
}
我希望这个解释可以帮助你。
如果你已经是一个平等的测试,你有没有希望。
假设你有一个情况下,每个元素都是唯一的。 而另一种只有两个元素是重复的。
有n(n+1)/2
的第二类型。 每一个都可以仅由一个特定的比较来自第一区别。 这意味着在最坏的情况下,你必须做的所有n(n+1)/2
的比较:在所有对exhastive搜索。
你需要做的是找出还有什么你真能做到,因为只有平等是极为罕见的。
文章来源: [only equal operator]what are the fast algorithms to find duplicate elements in a collection and group them?