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

问题描述

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

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}

在这里我们找到两个(非平凡的)范围，这些范围内的所有整数都存在于数组中，即 [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屋！