查找整数列表中最小的缺失元素 [英] Finding the smallest missing element in an integer list

问题描述

您好，

对于某些项目，我有一个字典，由整数键索引，可以分段（这就是为什么我没有使用一个列表）。例如，Keys集合可以包含{1,2,3,5,7}。

我有时必须在这个字典中插入一个元素，我想这样做，以便填充缺少的键。我想知道是否有一种方法使用Linq找到适当的索引来放置新值（在上面的例子中，表达式将返回4）。

任何想法？

谢谢，

Xavier

Hello,

For some project I have a dictionary, indexed by integer keys, that can be fragmented (which is why I did not use just a list). For example the Keys collection could contain {1, 2, 3, 5, 7}.

I sometimes have to insert an element in this dictionary, and I want to do it so it fills the missing keys. And I wondered if there was a way using Linq to find the appropriate index to put the new value at (in the above example, the expression would return 4).

Any ideas ?

Thanks,

Xavier

推荐答案

4年后可能关注的人：

To whom it may concern after 4 years:

因为您只对第一个缺失的密钥感兴趣，解决方案是：

Because you are only interested in the first missing key, the solution is:

int[] keys = { 1, 2, 3, 5, 7 };

var arrayWithFirstMissingKey = keys
    .Select((key, index) => new { Key = key, Index = index })
    .Where(tuple => (tuple.Index + 1 < keys.Length) && (keys[tuple.Index + 1] > tuple.Key +1))
    .Select(tuple => tuple.Key +1)
    .Take(1)
    .ToArray();

第一个 选择创建（Key，Index）元组，因为Enumerables不支持索引， 

The 1st  Select creates (Key, Index) tuples, because Enumerables don't support indexes, 

Where子句检测到与其后继有间隙的第一个密钥。

The Where clause detects the first key which has a gap to it's successor.

第二个选择确定缺口的第一个缺失密钥。

The 2nd select determines the first missing key of the gap.

在找到第一个缺失密钥后，Take子句可以防止不必要的开销。

The Take clause prevents unnecessary overhead after the first missing key is found.

这篇关于查找整数列表中最小的缺失元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！