查找數組中的連續範圍

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 implementation，隨着爲什麼它的工作原理更詳細的分析，爲什麼它有正確的運行時一起。它還探討了一些在算法初始描述中不明顯的邊緣情況（例如，如何處理整數溢出）。

希望這會有所幫助！

Answer 2

模板上面的答案將工作，但你不需要一個哈希表。散列可能需要很長時間，具體取決於您使用的算法。你可以詢問面試官是否有一個最大數量的整數，然後創建一個這樣大小的數組。調用它存在[]然後通過arr掃描並標記存在[i] = 1;然後迭代通過存在[]保持跟蹤4個變量，當前最大範圍的大小，以及當前最大範圍的開始，當前範圍的大小以及當前範圍的開始。當您看到存在[i] = 0時，比較當前範圍值與最大範圍值並根據需要更新最大範圍值。

如果沒有最大值，那麼你可能必須去與散列法。

Answer 3

該解決方案可以使用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]

Answer 4

其實考慮到我們只是排序整數，因此一個比較排序是沒有必要的，您可以使用Radix或BucketSort對數組進行排序，然後遍歷它。

簡單而肯定的受訪者希望聽到的不是，但還是正確的;）

Answer 5

Haskell的實現的格里戈爾·Gevorgyan的解決方案，從另一個誰沒有得到機會的question之前發佈被標記爲重複的...（僅更新哈希和最長的範圍，到目前爲止，在遍歷列表）

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) 

Answer 6

這是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; 
    } 
} 

其他方法here。

Answer 7

一個快速的方法來做到這一點（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)); 

Answer 8

我讀了很多關於多平臺解決方案，這個問題，一個得到了我的注意，因爲它解決了這個問題很典雅，很容易跟隨。

這種方法的主鏈是創建一組/散列這需要O（n）的時間，並從那裏每次訪問該組/散列將是O（1）。由於O型符號省略的常數項，這個算法仍然可以被整體描述爲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。

一切信用證斯特凡Pochmann。