16

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

{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[] 数组。

4

9 回答 9

10

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

首先将数组中的所有条目放入哈希表中。接下来，创建第二个哈希表来存储我们“访问过”的元素，该哈希表最初是空的。

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

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

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

希望这可以帮助！

于 2011-03-24T06:25:12.167 回答
8

该解决方案可以使用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]
于 2011-03-24T13:24:05.433 回答
1

这是Java中的解决方案：

public class Solution {  
    public int longestConsecutive(int[] num) {  
        int longest = 0;  
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();  
        for(int i = 0; i< num.length; i++){  
            map.put(num[i], false);  
        }  

        int l, k;  
        for(int i = 0;i < num.length;i++){  

            if(map.containsKey(num[i]-1) || map.get(num[i])) continue;  
            map.put(num[i], true);  
            l = 0; k = num[i];  
            while (map.containsKey(k)){  
                l++;  
                k++;  
            }  
            if(longest < l) longest = l;  

        }  
        return longest;  
    }  
}

其他方法在这里。

于 2015-07-31T07:19:10.583 回答
0

上面的模板答案将起作用，但您不需要哈希表。散列可能需要很长时间，具体取决于您使用的算法。你可以问面试官这个整数是否有最大数，然后创建一个该大小的数组。称它为exist[] 然后扫描arr并标记exist[i] = 1; 然后遍历存在 [] 跟踪 4 个变量、当前最大范围的大小、当前最大范围的开始、当前范围的大小和当前范围的开始。当您看到存在 [i] = 0 时，将当前范围值与最大范围值进行比较，并在需要时更新最大范围值。

如果没有最大值，那么您可能必须使用散列方法。

于 2011-03-24T06:41:29.887 回答
0

实际上考虑到我们只是对整数进行排序，因此不需要比较排序，您可以使用 Radix- 或 BucketSort 对数组进行排序，然后遍历它。

简单，当然不是受访者想听到的，但仍然是正确的；）

于 2011-03-24T15:43:24.003 回答
0

Grigor Gevorgyan 解决方案的 Haskell 实现，来自另一个在问题被标记为重复之前没有机会发布的人......（只需更新哈希和迄今为止的最长范围，同时遍历列表）

import qualified Data.HashTable.IO as H
import Control.Monad.Random

f list = do 
  h <- H.new :: IO (H.BasicHashTable Int Int)
  g list (0,[]) h where
    g []     best h = return best
    g (x:xs) best h = do 
      m <- H.lookup h x
      case m of
        Just _     -> g xs best h
        otherwise  -> do 
          (xValue,newRange) <- test
          H.insert h x xValue
          g xs (maximum [best,newRange]) h
       where 
         test = do
           m1 <- H.lookup h (x-1)
           m2 <- H.lookup h (x+1)
           case m1 of
             Just x1 -> case m2 of
                          Just x2 -> do H.insert h (x-1) x2
                                        H.insert h (x+1) x1
                                        return (x,(x2 - x1 + 1,[x1,x2]))
                          Nothing -> do H.insert h (x-1) x
                                        return (x1,(x - x1 + 1,[x,x1]))
             Nothing -> case m2 of
                          Just x2 -> do H.insert h (x+1) x
                                        return (x2,(x2 - x + 1,[x,x2]))
                          Nothing -> do return (x,(1,[x]))

rnd :: (RandomGen g) => Rand g Int
rnd = getRandomR (-100,100)

main = do
  values <- evalRandIO (sequence (replicate (1000000) rnd))
  f values >>= print

输出：

*Main> main
(10,[40,49])
(5.30 secs, 1132898932 bytes)
于 2013-07-11T23:23:39.650 回答
0

我在多个平台上阅读了很多关于这个问题的解决方案，其中一个引起了我的注意，因为它非常优雅地解决了这个问题，而且很容易理解。

这种方法的主干是创建一个需要 O(n) 时间的集合/散列，并且从那里每次访问集合/散列将是 O(1)。由于 O-Notation 省略了常数项，该算法总体上仍然可以描述为 O(n)

def longestConsecutive(self, nums):
    nums = set(nums)                    # Create Hash O(1)   
    best = 0
    for x in nums:                   
        if x - 1 not in nums:           # Optimization
            y = x + 1                   # Get possible next number
            while y in nums:            # If the next number is in set/hash
                y += 1                  # keep counting
            best = max(best, y - x)     # counting done, update best
    return best

如果你用简单的数字来处理它，那是直截了当的。当该特定数字是序列的第一个时，该Optimization步骤只是确保您开始计数的短路。beginning

斯特凡波赫曼的所有学分。

于 2017-11-18T07:22:07.430 回答
0

使用 Javascript 稀疏数组功能的非常短的解决方案：

O(n) 时间使用 O(n) 额外空间。

var arr = [2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15];

var a = [];
var count = 0, max_count = 0;

for (var i=0; i < arr.length; i++) a[arr[i]] = true;
for (i = 0; i < a.length; i++) {
    count = (a[i]) ? count + 1 : 0;
    max_count = Math.max(max_count, count);
    }

console.log(max_count); // 7
于 2020-06-06T21:57:52.577 回答
-1

一种快速的方法（PHP）：

$tab = array(14,12,1,5,7,3,4,10,11,8);
asort($tab);
$tab = array_values($tab);
$tab_contiguous = array();
$i=0;
foreach ($tab as $key => $val) {
    $tab_contiguous[$i][] = $tab[$key];
    if (isset($tab[$key+1])) {
        if($tab[$key] + 1 != $tab[$key+1])
            $i++;
    }
}
echo(json_encode($tab_contiguous));
于 2015-11-18T16:37:12.217 回答