logo标签列表

给定一个区间列表，寻找最大重叠区间的高效算法

c#algorithmmathdynamic-programming
10

考虑下面描述连续范围的 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)是不正确的，我对它的想法是错误的。正如评论中指出的那样，它应该是O(N * M)。
编辑2：让我规定一些事情，整数值的绝对最小值和最大值将从(0, 20000)开始。其次，IRange的平均数量将在100左右。我不知道这是否会改变算法的设计方式。
编辑3：我正在一个科学仪器（质谱仪）上实现这个算法，在这个仪器上，数据处理的速度对数据的质量至关重要（更快的分析时间=在时间T内收集更多的光谱）。固件语言（专有）只有数组[]，而且不是面向对象的。我选择C#，因为我擅长在这两种语言之间移植概念，并认为在SO社区的利益上，一个好的答案会有更广泛的受众。
如果我没记错的话，你可以使用双重循环来实现：for(var i = 0; i < array.length; i++) for(var j = i + 1; j < array.Length; j++) max = Math.max(max, GetOverlap(array[i], array[j])); - Alxandr
2
这不是O(N^2)；它是O(N*M)，其中N是范围的数量，M是域中的最大值。我自己想不出更好的方法，但一些聪明的人已经研究了类似这样的算法数十年。在网上搜索一下吧。 - Pieter Geerkens
我不明白你所说的“最大重叠范围”是什么意思。能否请您给出更多的例子？比如，如果有这样一些范围：1到5、2到6、4到10和15到20。 - Colonel Panic
1
@ColonelPanic 返回值将是4到5的范围。整数4和5出现在四个给定范围中的三个中。它们也是连续的，并且没有其他连续范围共享相同的模式（3）。将这些范围视为具有定义宽度和起始点的纸张。如果您将所有纸张叠放在一起（具有适当的偏移量），则堆叠最厚的位置在哪里？ - Moop
2个回答
10
将您的范围列表转换为起始点和终止点列表。使用O(n log n)算法对该列表进行排序。现在，您可以遍历该列表，并根据其是起始点还是终止点来递增或递减计数器，这将给您当前的重叠深度。
7
当你将所有这些操作结合起来时，时间复杂度为O(N log N)，比O(N^2)低。对于小数据集来说，可能会更慢，但它确实具有更低的渐进复杂度。 - Servy
你如何区分一个 int 是否为起点或终点？ - Moop
2
保留一个指示此项的字段。它可以是布尔值，或者可能是另一个整数，其值为“+1”或“-1”，因此您可以在任何情况下将其添加到深度值中。 - comingstorm
1
@Moop，如果你的空间受限，并且在你编辑的问题中指定了整数值，你可以将起始/停止值乘以2，并向其中一个添加1。不过这只是最后的选择，我建议使用comingstorm提出的其中一种方法。 - Mark Ransom
2
结果是，这种类型的问题通过将其转换为排序问题来解决，除非数据中存在其他关系，否则不会有比nlogn更快的算法。 - Tyler Durden
显示剩余2条评论
1

据我理解，OP的问题是关于给定3个范围的解决方案。

A: 012
B:  123
C:    34

将是范围为12（A和B的常见子集），不是 范围123（因为它不是任何一对的常见子集）。
在编写任何代码之前，先在纸上思考算法。动态规划是一个好的解决方案吗？（如果您不了解动态规划，请阅读相关书籍）。动态规划的想法是构建更简单的子问题的解决方案。
设f_i(n, k)为以n开头并且至少与前i个给定范围中的k个相同的最长间隔的大小。
您可以从f_0计算出f_1，从f_1计算出f_2等等。更新函数只取决于考虑的额外范围。
假设有M个范围。 f_M的值将告诉我们您的问题的答案。
您所讨论的最大深度是最大的k，使得对于某些n，f_M(n，k)非零。让我们称之为最大深度K。然后我们寻找f_M(n，K)在n上的最大值。最大值是您最大区间的大小，并始于最大化的n。
最大化的n必须是某些范围的下限，因此我们只需要为这些类型的n计算f。有M个范围，因此最多有M个下限。因此，此算法的复杂度为O(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。
在这种情况下，答案将是123，而不是12。 123是连续的，并且具有最大的模式/深度为2。 - Moop
那么问题就简单多了，你只需要计数。Mark解释了最快的方法。 - Colonel Panic
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接