查找数组中连续的范围 [英] Finding contiguous ranges in arrays

问题描述

您给出一个整数数组。你必须输出最大范围，使得在范围内的所有数字是present阵列中。这些数字可能是present任何顺序。例如，假设该阵列是

You are given an array of integers. You have to output the largest range so that all numbers in the range are present in the array. The numbers might be present in any order. For example, suppose that the array is

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

在这里，我们找到两个（平凡）的范围为它在这些范围内的所有整数为present阵中，分别是[2,8]和[10,12]。出于这些[2,8]是较长的一个。因此，我们需要输出。

Here we find two (nontrivial) ranges for which all the integers in these ranges are present in the array, namely [2,8] and [10,12]. Out of these [2,8] is the longer one. So we need to output that.

当我得到了这个问题，我被要求做这种线性的时间和不使用任何排序。我认为有可能是一个基于散列的解决方案，但我不能拿出任何东西。

When I was given this question, I was asked to do this in linear time and without using any sorting. I thought that there might be a hash-based solution, but I couldn't come up with anything.

下面是我尝试的解决方案：

Here's my attempt at a solution:

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 []数组应该被使用。

I am stuck at this part... I can't figure out how many tempanswer[] arrays should be used.

推荐答案

我认为以下解决方案将工作在O（n）的时间用O（n）的空间。

I think that the following solution will work in O(n) time using O(n) space.

通过将所有的条目的阵列中为哈希表开始。接下来，创建第二个哈希表存储，我们已分子参观，这最初是空的。

Begin by putting all of the entries in the array into a hash table. Next, create a second hash table which stores elements that we have "visited," which is initially empty.

现在，整个迭代的元素之一阵列的时间。对于每个元素，检查该元素是在被访问的集中。如果是这样，跳过它。否则，该元素计数向上。在每一步中，检查当前的数量是主要的哈希表所示。如果是的话，继续前进并标记电流值作为访问组的一部分。如果没有，请停止。接下来，重复此过程，除非向下计数。这告诉我们，在范围含有这种特定数组值的连续元素数。如果我们跟踪发现，这种方式最大的范围内，我们将有一个解决我们的问题。

Now, iterate across the array of elements one at a time. For each element, check if the element is in the visited set. If so, skip it. Otherwise, count up from that element upward. At each step, check if the current number is in the main hash table. If so, continue onward and mark the current value as part of the visited set. If not, stop. Next, repeat this procedure, except counting downward. This tells us the number of contiguous elements in the range containing this particular array value. If we keep track of the largest range found this way, we will have a solution to our problem.

该算法的运行时间复杂度为O（n）。看到这一点，请注意，我们可以在O（n）时间的第一步建立哈希表。接着，当我们开始扫描到阵列找到最大范围，每次扫描范围需要时间成比例的范围的长度。由于范围的长度的总和为原始数组中元素的数量，并且由于我们从未扫描相同的范围的两倍（因为我们标记每个我们访问号码），该第二步骤需要O（n）的时间作为那么，对于为O（n）的净运行时间

The runtime complexity of this algorithm is O(n). To see this, note that we can build the hash table in the first step in O(n) time. Next, when we begin scanning to array to find the largest range, each range scanned takes time proportional to the length of that range. Since the total sum of the lengths of the ranges is the number of elements in the original array, and since we never scan the same range twice (because we mark each number that we visit), this second step takes O(n) time as well, for a net runtime of O(n).

编辑：：如果您感到好奇，我有一个的的 Java实现 ，以及为什么它的工作原理和更详细的分析，为什么它有正确的版本。它还探讨不在算法（例如，如何处理整数溢出）。

If you're curious, I have a Java implementation of this algorithm, along with a much more detailed analysis of why it works and why it has the correct runtime. It also explores a few edge cases that aren't apparent in the initial description of the algorithm (for example, how to handle integer overflow).

希望这有助于！

这篇关于查找数组中连续的范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！