Encontrar rangos contiguos en matrices

Question

Se le da una matriz de enteros. Tienes que generar el rango más grande para que todos los números en el rango estén presentes en la matriz. Los números pueden estar presentes en cualquier orden. Por ejemplo, supongamos que la matriz es

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

Aquí encontramos dos (no trivial) rangos para la que todos los números enteros en estos intervalos están presentes en la matriz, es decir, [2,8] y [10,12]. Fuera de estos [2,8] es el más largo. Entonces tenemos que dar salida a eso.

Cuando me formularon esta pregunta, se me pidió que hiciera esto en tiempo lineal y sin usar ningún tipo de clasificación. Pensé que podría haber una solución basada en hash, pero no pude encontrar nada.

Aquí está mi intento de solución:

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 

estoy atascado en esta parte ... no puedo averiguar cuántas tempanswer [] se deben utilizar matrices.

Answer 1

Creo que la siguiente solución funcionará en el tiempo O (n) utilizando el espacio O (n).

Comience colocando todas las entradas del conjunto en una tabla hash. A continuación, cree una segunda tabla hash que almacene los elementos que hemos "visitado", que inicialmente está vacío.

Ahora, itere a través de la matriz de elementos uno a la vez. Para cada elemento, verifique si el elemento está en el conjunto visitado. Si es así, sáltelo. De lo contrario, cuente desde ese elemento hacia arriba. En cada paso, verifique si el número actual está en la tabla principal principal. De ser así, continúe y marque el valor actual como parte del conjunto visitado. Si no, para. A continuación, repita este procedimiento, excepto la cuenta regresiva. Esto nos dice la cantidad de elementos contiguos en el rango que contiene este valor de matriz en particular. Si hacemos un seguimiento del mayor rango encontrado de esta manera, tendremos una solución a nuestro problema.

La complejidad del tiempo de ejecución de este algoritmo es O (n). Para ver esto, tenga en cuenta que podemos construir la tabla hash en el primer paso en el tiempo O (n). Luego, cuando comenzamos a escanear a una matriz para encontrar el rango más grande, cada rango escaneado toma tiempo proporcional a la longitud de ese rango. Dado que la suma total de las longitudes de los rangos es la cantidad de elementos en el conjunto original, y dado que nunca escaneamos el mismo rango dos veces (porque marcamos cada número que visitamos), este segundo paso toma el tiempo O (n) como bien, para un tiempo de ejecución neto de O (n).

EDIT: Si tienes curiosidad, tengo un Java implementation de este algoritmo, junto con un análisis mucho más detallado de por qué funciona y qué tiene el tiempo de ejecución correcta. También explora algunos casos extremos que no son aparentes en la descripción inicial del algoritmo (por ejemplo, cómo manejar el desbordamiento de enteros).

Espero que esto ayude!

Answer 2

La respuesta anterior por plantilla funcionará pero no necesita una tabla hash. Hashing podría tomar un largo tiempo dependiendo de qué algoritmo utilice. Puede preguntar al entrevistador si hay un número máximo que puede ser el número entero, luego cree una matriz de ese tamaño. Llámalo existir [] Luego escanea a través de arr y marca existir [i] = 1; Luego itere a través de exist [] manteniendo un registro de 4 variables, tamaño del rango actual más grande y el comienzo del rango actual más grande, el tamaño del rango actual y el comienzo del rango actual. Cuando vea que existe [i] = 0, compare los valores de rango actuales con los valores de rango más grandes y actualice los valores de rango más grandes si es necesario.

Si no hay ningún valor máximo entonces es posible que tenga que ir con el método de hash.

Answer 3

La solución podría utilizar 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) + "]"); 
    } 
}

Muestra I/O:

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

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

Answer 4

considerando hecho de que sólo estamos clasificando los números enteros y, por tanto, una especie comparación no es necesario, usted puede simplemente ordenar la matriz usando un Radix o BucketSort y luego iterar a través de él.

simple y ciertamente no es lo que el entrevistado quería escuchar, pero es correcto, sin embargo;)

Answer 5

aplicación

Un Haskell de la solución de Grigor Gevorgyan, de otro que no tienen la oportunidad de publicar antes de la question se caracterizó como una duplicar ... (simplemente actualiza el hash y el rango más largo hasta ahora, al recorrer la lista)

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 

salida:

*Main> main 
(10,[40,49]) 
(5.30 secs, 1132898932 bytes) 

Answer 6

Aquí está la solución en 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; 
    } 
} 

otros enfoques here.

Answer 7

Una forma rápida de hacerlo (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

He leído un montón de soluciones en múltiples plataformas a este problema y uno me llamó la atención, ya que resuelve el problema muy elegante y es fácil seguir.

La columna vertebral de este método es crear un sistema/de hash que lleva tiempo O (n) y desde allí cada acceso al conjunto/de hash será O (1). Como términos constantes del Omitir notación O, siendo este algoritmo puede describirse en general como 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 

Es sencillo si se ejecutó sobre él con números simples. El paso Optimization es sólo un corto-circuito para asegurarse de que empiece a contar, cuando ese número específico es el beginning de una secuencia.

Todos los créditos a Stefan Pochmann.