arrays - sheet - Encontrar rangos contiguos en matrices

space complexity algorithm

Question

Te dan una matriz de enteros. Tiene 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 rangos (no triviales) para los cuales todos los enteros en estos rangos están presentes en la matriz, a saber, [2,8] y [10,12]. De estos [2,8] es el más largo. Así que tenemos que sacar eso.

Cuando me dieron esta pregunta, me pidieron que hiciera esto en tiempo lineal y sin usar ninguna clasificación. Pensé que podría haber una solución basada en hash, pero no pude encontrar nada.

Aquí está mi intento de una 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 matrices de tempanswer [] se deben usar.

Answer 1

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 2

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

Comience por poner todas las entradas de la matriz 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, iterar 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í, omítelo. De lo contrario, cuenta desde ese elemento hacia arriba. En cada paso, verifique si el número actual está en la tabla hash principal. Si es así, continúe y marque el valor actual como parte del conjunto visitado. Si no, detente. A continuación, repita este procedimiento, excepto contando hacia abajo. Esto nos dice el número de elementos contiguos en el rango que contiene este valor de matriz particular. Si hacemos un seguimiento del rango más grande 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 O (n). A continuación, cuando comenzamos a escanear a la matriz para encontrar el rango más grande, cada rango escaneado toma un tiempo proporcional a la longitud de ese rango. Dado que la suma total de las longitudes de los rangos es el número de elementos en la matriz original, y como nunca escaneamos el mismo rango dos veces (porque marcamos cada número que visitamos), este segundo paso toma O (n) tiempo como Bueno, para un tiempo de ejecución neto de O (n).

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

¡Espero que esto ayude!

Answer 3

En realidad, considerando que solo estamos clasificando enteros y, por lo tanto, NO es necesaria una ordenación de comparación, simplemente puede ordenar la matriz utilizando un Radix- o BucketSort y luego iterarla.

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

Answer 4

La respuesta anterior por plantilla funcionará pero no necesita una tabla hash. El hash puede tardar mucho tiempo dependiendo del algoritmo que utilice. Puede preguntarle al entrevistador si hay un número máximo que puede ser el número entero, luego crear una matriz de ese tamaño. Llámelo existente [] Luego escanee arr y marque existiendo [i] = 1; Luego, iterar hasta que exista [] manteniendo un registro de 4 variables, el tamaño del rango más grande actual, y el comienzo del rango más grande actual, el tamaño del rango actual y el comienzo del rango actual. Cuando vea que existe [i] = 0, compare los valores de rango actuales frente a los valores de rango más grandes y actualice los valores de rango más grandes si es necesario.

Si no hay un valor máximo, es posible que tenga que ir con el método de hashing.

Answer 5

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 6

Leí muchas soluciones en múltiples plataformas a este problema y una me llamó la atención, ya que resuelve el problema de manera muy elegante y es fácil de seguir.

La columna vertebral de este método es crear un conjunto / hash que lleva un tiempo O (n) y desde allí cada acceso al conjunto / hash será O (1). Como la notación O omite los términos constantes, este algoritmo aún puede ser descrito 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 lo pasaste con números simples. El paso de Optimization es solo un cortocircuito para asegurarse de que comienza a contar, cuando ese número específico es el beginning de una secuencia.

Todos los créditos a Stefan Pochmann.

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

Una implementación de Haskell de la solución de Grigor Gevorgyan, de otro que no tuvo la oportunidad de publicar antes de que la question fuera marcada como un duplicado ... (simplemente actualiza el hash y el rango más largo hasta el momento, mientras recorre 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)