我有一个List<int>
,其中包含1,2,4,7,9例如。按顺序检查丢失的数字
我有10
的范围为0有没有办法来确定哪些号码在顺序都缺失了?
我认为LINQ可能会提供一个选项,但我看不到一个
在现实世界中我还可以列举包含100,000个项目因此性能是关键
我有一个List<int>
,其中包含1,2,4,7,9例如。按顺序检查丢失的数字
我有10
的范围为0有没有办法来确定哪些号码在顺序都缺失了?
我认为LINQ可能会提供一个选项,但我看不到一个
在现实世界中我还可以列举包含100,000个项目因此性能是关键
var list = new List<int>(new[] { 1, 2, 4, 7, 9 });
var result = Enumerable.Range(0, 10).Except(list);
+1简单和干净 – 2010-03-19 08:21:49
绝对简单和干净 - 但速度问题如果范围很大 – 2010-03-19 08:24:52
我可以拥有此2.0请 – Vivekh 2011-09-02 12:29:19
把你要检查的范围转换为HashSet:
public IEnumerable<int> FindMissing(IEnumerable<int> values)
{
HashSet<int> myRange = new HashSet<int>(Enumerable.Range(0,10));
myRange.ExceptWith(values);
return myRange;
}
将返回不在values
中的值。
我这样做的原因是大量的序列,这应该更快,因为通过遍历输入列表并删除每个元素来减少哈希集。 Except迭代器方法迭代集合中每个元素的输入集合。 – 2010-03-19 08:21:04
'HashSet
有更新代码示例 - 只是意识到,当你发布该评论! – 2010-03-19 08:26:17
LINQ的Except
方法将是最可读的。它是否适合你的工作将是测试的问题。
E.g.
range.Except(listOfValues);
编辑
下面是我用我的小基准测试程序,为他人堵塞逃脱:
static void Main()
{
var a = Enumerable.Range(0, 1000000);
var b = new List<int>();
for (int i = 0; i < 1000000; i += 10)
{
b.Add(i);
}
Stopwatch sw = new Stopwatch();
sw.Start();
var c = a.Except(b).ToList();
sw.Stop();
Console.WriteLine("Milliseconds {0}", sw.ElapsedMilliseconds);
sw.Reset();
Console.ReadLine();
}
超过一半。而不是只发布基准代码,你也可以发布你的结果。这个问题已经得到解答,但对于其他人来说,对速度和“foreach”很好奇,例如,如果您有结果,您的答案就会变得有用。 – 2012-08-05 19:01:02
创建的NUM项的数组
const int numItems = 1000;
bool found[numItems] = new bool[numItems];
List<int> list;
PopulateList(list);
list.ForEach(i => found[i] = true);
// now iterate found for the numbers found
for(int count = 0; i < numItems; ++numItems){
Console.WriteList("Item {0} is {1}", count, found[count] ? "there" : "not there");
}
这个答案有什么问题? – 2010-03-19 09:27:13
1.您正在强制使用List <>对象; 2.你正在创建一个非常大的中间对象(你的布尔数组)。 3.这不是一个干净可读的解决方案,请看其他人。 – 2010-03-21 19:55:03
谢谢。我不介意被投票的答案,我只是希望我原来被告知原因,这样我就可以学习。再次谢谢你 – 2010-03-21 23:36:54
List<int> selectedNumbers = new List<int>(){8, 5, 3, 12, 2};
int firstNumber = selectedNumbers.OrderBy(i => i).First();
int lastNumber = selectedNumbers.OrderBy(i => i).Last();
List<int> allNumbers = Enumerable.Range(firstNumber, lastNumber - firstNumber + 1).ToList();
List<int> missingNumbers = allNumbers.Except(selectedNumbers).ToList();
foreach (int i in missingNumbers)
{
Response.Write(i);
}
如果范围是可预测的,我建议以下解决方案:
public static void Main()
{
//set up the expected range
var expectedRange = Enumerable.Range(0, 10);
//set up the current list
var currentList = new List<int> {1, 2, 4, 7, 9};
//get the missing items
var missingItems = expectedRange.Except(currentList);
//print the missing items
foreach (int missingItem in missingItems)
{
Console.WriteLine(missingItem);
}
Console.ReadLine();
}
问候, y00daa
这不使用LINQ,但在线性时间工作。
我假设输入列表是排序的。
这需要O(list.Count)
。
private static IEnumerable<int> get_miss(List<int> list,int length)
{
var miss = new List<int>();
int i =0;
for (i = 0; i < list.Count - 1; i++)
{
foreach (var item in
Enumerable.Range(list[i] + 1, list[i + 1] - list[i] - 1))
{
yield return item;
}
}
foreach (var item in Enumerable.Range(list[i]+1,length-list[i]))
{
yield return item;
}
}
这应该采取O(n)
其中n是全范围长度。
static void Main()
{
List<int> identifiers = new List<int>() { 1, 2, 4, 7, 9 };
Stopwatch sw = new Stopwatch();
sw.Start();
List<int> miss = GetMiss(identifiers,150000);
sw.Stop();
Console.WriteLine("{0}",sw.ElapsedMilliseconds);
}
private static List<int> GetMiss(List<int> identifiers,int length)
{
List<int> miss = new List<int>();
int j = 0;
for (int i = 0; i < length; i++)
{
if (i < identifiers[j])
miss.Add(i);
else if (i == identifiers[j])
j++;
if (j == identifiers.Count)
{
miss.AddRange(Enumerable.Range(i + 1, length - i));
break;
}
}
return miss;
}
好的,真的,创建一个新的列表,它与最初的列表并行运行除了它之外......
我创建使用Aggregate
方法,而不是找missings完全LINQ答案:
var list = new List<int>(new[] { 1, 2, 4, 7, 9 }); // Assumes list is ordered at this point
list.Insert(0, 0); // No error checking, just put in the lowest and highest possibles.
list.Add(10); // For real world processing, put in check and if not represented then add it/them.
var missing = new List<int>(); // Hold any missing values found.
list.Aggregate ((seed, aggr) => // Seed is the previous #, aggr is the current number.
{
var diff = (aggr - seed) -1; // A difference between them indicates missing.
if (diff > 0) // Missing found...put in the missing range.
missing.AddRange(Enumerable.Range((aggr - diff), diff));
return aggr;
});
丢失的列表中有此之后,上面的代码已被执行:
3, 5, 6, 8
任何两个IEnunumerable<T>
其中T :
IComparable
一般工作的替代方法。如果两个IE枚举都是排序的,则这在O(1)存储器(即,没有创建另一个ICollection
并减去等)和在O(n)时间中起作用。
使用IEnumerable<IComparable>
和GetEnumerator
使这个可读性稍差,但更一般。
实施
/// <summary>
/// <para>For two sorted IEnumerable<T> (superset and subset),</para>
/// <para>returns the values in superset which are not in subset.</para>
/// </summary>
public static IEnumerable<T> CompareSortedEnumerables<T>(IEnumerable<T> superset, IEnumerable<T> subset)
where T : IComparable
{
IEnumerator<T> supersetEnumerator = superset.GetEnumerator();
IEnumerator<T> subsetEnumerator = subset.GetEnumerator();
bool itemsRemainingInSubset = subsetEnumerator.MoveNext();
// handle the case when the first item in subset is less than the first item in superset
T firstInSuperset = superset.First();
while (itemsRemainingInSubset && supersetEnumerator.Current.CompareTo(subsetEnumerator.Current) >= 0)
itemsRemainingInSubset = subsetEnumerator.MoveNext();
while (supersetEnumerator.MoveNext())
{
int comparison = supersetEnumerator.Current.CompareTo(subsetEnumerator.Current);
if (!itemsRemainingInSubset || comparison < 0)
{
yield return supersetEnumerator.Current;
}
else if (comparison >= 0)
{
while (itemsRemainingInSubset && supersetEnumerator.Current.CompareTo(subsetEnumerator.Current) >= 0)
itemsRemainingInSubset = subsetEnumerator.MoveNext();
}
}
}
使用
var values = Enumerable.Range(0, 11);
var list = new List<int> { 1, 2, 4, 7, 9 };
var notIncluded = CompareSortedEnumerables(values, list);
作为向安德拉斯,100万个整数的范围,10万一个列表中的注释表明,使用除(我的机器上)需要0.25秒。但是我们无法知道它是否足以满足您的要求(如果不是,那么可接受的性能限制是什么?) – 2010-03-19 08:30:52