c# – 如何快速判断一个列表是否只包含重复项？

发布时间：2020-12-15 06:50:43 所属栏目：百科来源：网络整理

导读：有多个相关问题,但我正在寻找一个与我的案例相关的解决方案.有一个(通常)14个整数的数组.如何快速判断每个int是否出现两次(即有7对)？值范围从1到35.这里的主要方面是性能. 作为参考,这是我目前的解决方案.它的写作类似于规范,尽可能的紧密,不考虑性能,所以

有多个相关问题,但我正在寻找一个与我的案例相关的解决方案.有一个(通常)14个整数的数组.如何快速判断每个int是否出现两次(即有7对)？值范围从1到35.这里的主要方面是性能.

作为参考,这是我目前的解决方案.它的写作类似于规范,尽可能的紧密,不考虑性能,所以我肯定可以大大改进：

var pairs = Array
    .GroupBy (x => x)
    .Where (x => x.Count () == 2)
    .Select (x => x.ToList ())
    .ToList ();
IsSevenPairs = pairs.Count == 7;

使用Linq是可选的.我不在乎如何,只要它很快:)

编辑：有一个特殊情况,int出现2n次,n>在这种情况下,支票应该失败,即应该有7个不同的对.

编辑：结果
我测试了Ani和Jon的解决方案,并在目标应用程序中的多个基准测试中发现,Ani’s在我的机器上有两倍的吞吐量(Win7-64上的一些Core 2 Duo).生成int数组已经需要与相应的检查一样长的时间,所以我对结果感到满意.谢谢,所有！

解决方法

显然,LINQ不会在这里提供最佳解决方案,尽管我将改进您当前的LINQ解决方案：

// checks if sequence consists of items repeated exactly once
bool isSingleDupSeq = mySeq.GroupBy(num => num)
                           .All(group => group.Count() == 2);

// checks if every item comes with atleast 1 duplicate
bool isDupSeq = mySeq.GroupBy(num => num)
                     .All(group => group.Count() != 1);

对于具体情况,您提到(0 – 31),这是一个更快速的基于阵列的解决方案.当可能数字的范围很大(在这种情况下使用散列解决方案))时,它不会很好地扩展.

// elements inited to zero because default(int) == 0
var timesSeenByNum = new int[32];

foreach (int num in myArray)
{
    if (++timesSeenByNum[num] == 3)
    {
        //quick-reject: number is seen thrice
        return false;
    }
}

foreach (int timesSeen in timesSeenByNum)
{
    if (timesSeen == 1)
    {
        // only rejection case not caught so far is
        // if a number is seen exactly once
        return false;
    }
}

// all good,a number is seen exactly twice or never
return true;

编辑：修正了Jon Skeet指出的错误.我也应该指出,他的算法更聪明,也许更快.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!