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

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

编辑 3

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

4

2 回答 2

10

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

于 2013-03-06T17:16:02.613 回答
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，使得 f_M(n, k) 对于某些 n 不为零。我们称其为最大深度 K。然后我们在 n 上寻找 f_M(n, K) 的最大值。它的最大值是您的最大范围的大小，从最大化 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 开始。

于 2013-03-06T19:41:12.237 回答