有多个相关问题,但我正在寻找一个与我的案例相关的解决方案.有一个(通常)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指出的错误.我也应该指出,他的算法更聪明,也许更快.
