在给定范围列表中寻找最大重叠范围的有效算法

本文关键字：范围 重叠 有效 算法 寻找 列表 | 更新日期: 2023-09-27 18:02:40

考虑下面描述integer值连续范围的接口。

public interface IRange {
    int Minimum { get;}
    int Maximum { get;}
    IRange LargestOverlapRange(IEnumerable<IRange> ranges);
}

我正在寻找一种有效的算法来找到给定IRange对象列表的最大重叠范围。下面的图表简要地概述了这个想法。其中顶部数字代表integer值，|-----|代表具有最小值和最大值的IRange对象。我堆叠了IRange对象，这样解决方案就很容易可视化。

0123456789  ...                            N
|-------|   |------------|        |-----|
   |---------|    |---|
       |---|             |------------|
               |--------|  |---------------|
                              |----------|

这里，LargestOverlapRange方法将返回:

                                  |---|

因为这个范围总共有4个"重叠"。如果有两个独立的IRange有相同数量的重叠，我想返回null。

下面是我尝试的一些简短代码。

public class Range : IRange 
{
    public IRange LargestOverlapRange(IEnumerable<IRange> ranges) {           
        int maxInt = 20000;    
        // Create a histogram of the counts
        int[] histogram = new int[maxInt];
        foreach(IRange range in ranges) {
            for(int i=range.Minimum; i <= range.Maximum; i++) {
                histogram[i]++;
            }
        }
        // Find the mode of the histogram
        int mode = 0;
        int bin = 0;
        for(int i =0; i < maxInt; i++) {
            if(histogram[i] > mode) {
                mode = histogram[i];
                bin = i;
            }
        }
        // Construct a new range of the mode values, if they are continuous
        Range range;
        for(int i = bin; i < maxInt; i++) {
            if(histogram[i] == mode) {  
                if(range != null)
                    return null; // violates two ranges with the same mode   
                range = new Range();             
                range.Minimum = i;                     
                while(i < maxInt && histrogram[i] == mode)
                    i++;
                range.Maximum = i;                    
            }
        }
        return range;
    }
}

这包含四个循环，如果不更高，很容易得到O(n^2)。是否有一个更有效的算法(速度方面)从其他范围的列表中找到最大的重叠范围?

编辑

是的，O(n^2)是不正确的，我想错了。它应该是0 (N * M)，正如在评论中指出的那样。

编辑2

让我规定一些事情，integer值的绝对最小值和最大值将从(0,20000)开始。其次，IRange的平均数量将在100左右。我不知道这是否会改变算法的设计方式。

编辑3

我正在科学仪器(质谱仪)上实现该算法，其中数据处理的速度对数据质量至关重要(更快的分析时间=在时间T中收集的更多光谱)。固件语言(专有)只有阵列[]并且不是面向对象的。我之所以选择c#，是因为我很擅长在这两种语言之间移植概念，而且我认为，为了SO社区的利益，一个好的答案会有更广泛的受众。

在给定范围列表中寻找最大重叠范围的有效算法

将范围列表转换为起始点和停止点列表。用O(n log n)算法对列表排序。现在您可以遍历列表，并根据它是开始点还是停止点来增加或减少计数器，这将为您提供当前的重叠深度。

根据我对OP问题的理解，给定3个范围的解决方案

A: 012
B:  123
C:    34

将是范围12 (a和B的公共子集)，而不是范围123(因为它不是任何一对的公共子集)。

在写任何代码之前，先考虑一下纸上的算法。那么动态规划解决方案呢?(如果您不了解动态规划，值得在书中阅读)。动态规划的思想是建立更简单子问题的解。

设f_i(n, k)为前i个给定区间中从n开始到至少k的最长区间的大小。

可以从f_0求出f_1，从f_1求出f_2，以此类推。更新函数只取决于所考虑的一个额外范围。

假设有M个范围。f_M的值将告诉我们问题的答案。

你所说的最深深度是最大的k，使得f_M(n, k)对于某个n不为零。我们称之为最大深度k。然后我们寻找f_M(n, k)/n的最大值。它的最大值是你的最大范围的大小，它从最大n开始。

最大的n一定是某个范围的下界，所以对于这种n我们只需要计算f。有M个范围，所以最多有M个下界。因此，该算法的复杂度为0 (MMK)。

设第i个范围从a到b

如果n在a到b之外，则不改变
f_i(n,k) = f_i-1(n,k)

如果n在a到b之间，我们将新的区间与旧的k-1深度解结合来测试k深度解。只有当它比我们已有的更好时，我们才会使用它。f_i(n,k) = max ( f_i-1(n,k) , min( f_i-1(n,k-1) , b-n+1))

的例子!0 ~ 5、2 ~ 6、4 ~ 8、6 ~ 9。

n           0123456789
            ......          range 0 to 5
f_1(n,1)    6543210000
              .....         range 2 to 6
f_2(n,1)    6554321000
f_2(n,2)    0043210000
                .....       range 4 to 8
f_3(n,1)    6554543210  
f_3(n,2)    0043321000
f_3(n,3)    0000210000
                  ....      range 6 to 9
f_4(n,1)    6554544321
f_4(n,2)    0043323210
f_4(n,3)    0000211000
f_4(n,4)    0000000000

则最深深度K为3，最长范围为4 ~ 5。我们还可以看到，深度2的最大范围为4，从3开始。

相关文章：