1

假设我们有一个元素集合，而这些元素只有相等运算符。因此，不可能对它们进行排序。

你怎么能挑出那些有重复的，并把它们放在每组中比较少的？最好用 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
4

3 回答 3

3

找到任意谓词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。Less-then 满足这个性质，因此更大-then。但它们远非唯一的可能性。

您现在可以按 predicate 对集合进行排序P，所有相等的元素将是相邻的。在您的情况下，请定义P(E1,E2)=true, P(E2,E3)=true等。

于 2013-07-19T08:04:55.163 回答
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;
    }
}

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

于 2013-07-19T07:50:32.183 回答
2

如果你只有一个平等测试，你就没有希望了。

假设您遇到每个元素都是唯一的情况。另一个只有两个元素是重复的。

还有n(n+1)/2第二种。每个只能通过特定的比较与第一个区分开来。这意味着在最坏的情况下，您必须进行所有n(n+1)/2比较：对所有对进行全面搜索。

你需要做的是弄清楚你还能做什么，因为只有平等是极其罕见的。

于 2013-07-19T08:22:55.057 回答