查找序列中缺失和重叠的数字

本文关键字：重叠 数字 查找 | 更新日期: 2023-09-27 18:05:29

假设我们有一个这样的数据结构:

var sequences = new List<Tuple<int, int>>
                {
                    new Tuple<int, int>(1, 10),
                    new Tuple<int, int>(8, 101),
                    new Tuple<int, int>(102, 103),
                    new Tuple<int, int>(104, 104),
                    new Tuple<int, int>(110, 200)
                };

我想从这个集合中得到两个结果:

  • 所有缺失的数字(在本例中:105、106、107、108、109)
  • 所有重叠的数字(在这个例子中:8,9,10)

我可以用几个循环和helper集合编写一个算法。这当然会工作，但我想知道这是否可以在LINQ和/或其他更简单和更短的算法的帮助下实现?

编辑:上面例子中的数据结构表示5个序列，第一个序列包含从1到10的数字，第二个序列包含从8到101的数字，等等……因为在生产中，序列可能更大(多达数百万)，所以它们不是用实际的集合表示的(例如用包含所有数字的列表)，而是用Tuples表示，Tuples表示每个序列的最小和最大数量。

查找序列中缺失和重叠的数字

你可以通过

var missing = 
      Enumerable.Range(1, 200)
               .Where(i => sequences.All(t => t.Item1 > i || t.Item2 < i));
var overlapping = 
      Enumerable.Range(1, 200)
                .Where(i => sequences.Count(t => t.Item1 <= i && t.Item2 >= i) > 1);

我知道这个问题的算法(它是伪代码)。(复杂度类O(nlog(n))，其中n为元组的计数)

解决方案是sort Tuple by function:

  int comparer( Tuple a, Tuple b) {
      if ( a.first.compareTo(b.first) == 0 ) {
          return a.second.compareTo(b.second);
      } else 
          return a.first.compareTo(b.first);
  }

，所以示例元组:(1,10)，(1,5)，(2,8)将排序到:(1,5)， (1,10)， (2,8).

下一步是累积这个结果。迭代此结果并:

 Tuple result = SortedList[0];
 foreach ( Tuple tuple in SortedList ) {
     if ( result.second < tuple.first ) {
        // here you have missing number (result.second, tuple.first)
        result.first = tuple.first; 
        result.second = tuple.second
     } else if ( result.second > tuple.first ) {
        // here you have overlapping number (tuple.first, min( result.second,tuple.second ))
        if ( result.second < tuple.second ) {
              result.second = tuple.second;
        }
     } else {
        result.second = tuple.second;
     }
 }

我们所知道的是，if将在下一个元组的第一个数字大于或等于result.first时进行迭代。代码注释告诉你哪里有重叠和缺失的数字

try this

var expandedSequences = sequences.Select(t => Enumerable.Range(t.Item1, t.Item2-t.Item1)).SelectMany(t => t).OrderBy(i => i);
var dupes = expandedSequences.GroupBy(i => i).Where(g => g.Count() > 1).Select(g => g.Key);
var missing = Enumerable.Range(expandedSequences.Min(), expandedSequences.Max()).Except(expandedSequences);

一次:

var sequences = new List<Tuple<int, int>>
    {
        new Tuple<int, int>(1, 10),
        new Tuple<int, int>(8, 101),
        new Tuple<int, int>(102, 103),
        new Tuple<int, int>(104, 104),
        new Tuple<int, int>(110, 200)
    };
var missing = new List<int>();
var overlap = new List<int>();
sequences.Aggregate((prev, current) => {
    if (prev.Item2 >= current.Item1) {
        overlap.AddRange(Enumerable.Range(current.Item1, prev.Item2 - current.Item1 + 1));
    }
    if (current.Item1 > prev.Item2 + 1) {
        missing.AddRange(Enumerable.Range(prev.Item2 + 1, current.Item1 - prev.Item2 - 1));
    }
    return current;
});

有一些边缘情况，我只能假设您希望如何处理。我选择不处理其中一个(在代码中注释)。由于您没有给出如何表示缺失/重叠序列的指示，因此我选择了您自己的格式，使用元组来标识序列的开始和结束。

//Assumes they are sorted on item1
        Tuple<IEnumerable<Tuple<int,int>>,IEnumerable<Tuple<int,int>>> FindMissingAndOverLapping(IEnumerable<Tuple<int,int>> sequences){
            var previous = Tuple.Create(0, 0);
            var missing = new List<Tuple<int,int>>();
            var overlapping = new List<Tuple<int, int>>();
            var max = 0;
            foreach (var sequence in sequences){
                var end = previous.Item2;
                max = end > max ? end : max;
                if (previous.Item2 < sequence.Item1 + 1){
                    missing.Add(Tuple.Create(previous.Item2 + 1, sequence.Item1 - 1));
                } else if (max < sequence.Item1){
                    overlapping.Add(Tuple.Create(sequence.Item1, max));
                }
            }
            //The sequences in ovrelapping can be ovrelapping them self
            return new Tuple<IEnumerable<Tuple<int,int>>,IEnumerable<Tuple<int,int>>>(missing, overlapping);
        }
相关文章：