在数组中查找连续范围

Question

您将获得一个整数数组.您必须输出最大范围,以便该范围内的所有数字都存在于数组中.这些数字可能以任何顺序出现.例如,假设数组是

{2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15}

在这里,我们找到两个(非平凡的)范围,这些范围中的所有整数都存在于数组中,即[2,8]和[10,12].其中[2,8]是较长的一个.所以我们需要输出它.

当我收到这个问题时,我被要求在线性时间内完成此操作而不使用任何排序.我认为可能存在基于散列的解决方案,但我无法想出任何东西.

这是我尝试解决方案:

void printRange(int arr[])
{
    int n=sizeof(arr)/sizeof(int);
    int size=2;
    int tempans[2]; 

    int answer[2];// the range is stored in another array
    for(int i =0;i<n;i++)
    {
        if(arr[0]<arr[1])
        {
             answer[0]=arr[0];
             answer[1]=arr[1];
        }
        if(arr[1]<arr[0])
        {
            answer[0]=arr[1];
            answer[1]=arr[0];
        }

        if(arr[i] < answer[1])
            size += 1;
        else if(arr[i]>answer[1]) {
            initialize tempans to new range;
             size2=2;
        }
        else { 
            initialize tempans  to new range
        }
}

//I have to check when the count becomes equal to the diff of the range

我被困在这一部分......我无法弄清楚应该使用多少tempanswer []数组.

Answer 1

我认为以下解决方案将使用O(n)空间在O(n)时间内工作.

首先将数组中的所有条目放入哈希表中.接下来,创建第二个哈希表,它存储我们"访问过"的元素,这些元素最初是空的.

现在,一次迭代一个元素数组.对于每个元素,检查元素是否在访问集中.如果是这样,请跳过它.否则,从该元素向上计数.在每个步骤中,检查当前数字是否在主哈希表中.如果是这样,继续向前并将当前值标记为访问集的一部分.如果没有,停止.接下来,重复此过程,向下计数除外.这告诉我们包含此特定数组值的范围中的连续元素的数量.如果我们跟踪这种方式找到的最大范围,我们将解决我们的问题.

该算法的运行时复杂度为O(n).要看到这一点,请注意我们可以在O(n)时间的第一步中构建哈希表.接下来,当我们开始扫描到阵列以找到最大范围时,扫描的每个范围花费的时间与该范围的长度成比例.由于范围长度的总和是原始数组中元素的数量,并且因为我们从不扫描相同的范围两次(因为我们标记了我们访问的每个数字),所以第二步需要O(n)时间好吧,对于O(n)的净运行时间.

编辑:如果你很好奇,我有这个算法的Java实现,以及更详细的分析它为什么工作以及为什么它具有正确的运行时.它还探讨了一些在算法的初始描述中不明显的边缘情况(例如,如何处理整数溢出).

希望这可以帮助!

Answer 2

解决方案可以使用BitSet:

public static void detect(int []ns) {
    BitSet bs = new BitSet();
    for (int i = 0; i < ns.length; i++) {
        bs.set(ns[i]);
    }
    int begin = 0;
    int setpos = -1;
    while((setpos = bs.nextSetBit(begin)) >= 0) {
        begin = bs.nextClearBit(setpos);
        System.out.print("[" + setpos + " , " + (begin - 1) + "]");
    }
}

样本I/O:

detect(new int[] {2,10, 3, 12, 5,4, 11, 8, 7, 6, 15} );

[2,8] [10,12] [15,15]