-->

[只相当于运营商]什么是快速算法找到一个集合,他们组重复的元素?([only equal opera

2019-10-18 09:10发布

假设我们有元素的集合,这些元素只有平等的运营商。 因此,它是不可能对它们进行排序。

你怎么能挑选出那些有重复,并把它们放到各组比较的量最少? 优选在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

Answer 1:

它足以找到任意谓词P ,使得P(a,a)==falseP(a,b) && P(b,a)==falseP(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 ,等等。



Answer 2:

对于你的答案,但我相信,你想这仅仅是不是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;
    }
}

我希望这个解释可以帮助你。



Answer 3:

如果你已经是一个平等的测试,你有没有希望。

假设你有一个情况下,每个元素都是唯一的。 而另一种只有两个元素是重复的。

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?