algorithm - maximo - Subarreglo más largo cuyos elementos forman una secuencia continua.

maximo subarreglo

Question

Dada una matriz no clasificada de enteros positivos, encuentre la longitud del subarreglo más largo cuyos elementos cuando están ordenados son continuos. ¿Puedes pensar en una solución O (n)?

Ejemplo:

{10, 5, 3, 1, 4, 2, 8, 7}, la respuesta es 5.

{4, 5, 1, 5, 7, 6, 8, 4, 1}, la respuesta es 5.

Para el primer ejemplo, el subarreglo {5, 3, 1, 4, 2} cuando se clasifica puede formar una secuencia continua 1,2,3,4,5, que es la más larga.

Para el segundo ejemplo, el subarray {5, 7, 6, 8, 4} es el subarray de resultados.

Puedo pensar en un método que para cada subarreglo, verificar si (máximo - mínimo + 1) es igual a la longitud de ese subarreglo, si es verdadero, entonces es un subarreglo continuo. Toma el más largo de todos. Pero es O (n ^ 2) y no puede tratar con duplicados.

¿Alguien puede dar un mejor método?

Answer 1

Aquí hay 3 soluciones aceptables:

El primero es O(nlog(n)) en el tiempo y O(n) espacio, el segundo es O(n) en el tiempo y O(n) en el espacio, y el tercero es O(n) en el tiempo y O(1) en el espacio.

1. construye un binary search tree luego recórralo en orden .
   mantenga 2 punteros uno para el inicio del subconjunto máximo y uno para el final. mantenga el valor max_size mientras itera el árbol. es una complejidad de tiempo y espacio O(n*log(n)) .

2. siempre puede ordenar los números configurados usando el orden de conteo en un tiempo lineal y ejecutar la matriz, lo que significa O(n) tiempo y complejidad de espacio.

3. Suponiendo que no hay un desbordamiento o un tipo de datos entero grande. Suponiendo que la matriz es un conjunto matemático (sin valores duplicados). Puedes hacerlo en O(1) de memoria:

   • Calcula la suma de la matriz y el producto de la matriz.
   • Calcule qué números tiene en él asumiendo que tiene el mínimo y el máximo del conjunto original. Totalmente es O(n) complejidad del tiempo.

Answer 2

Algoritmo para resolver problema original en O (n) sin duplicados . Tal vez, ayuda a alguien a desarrollar una solución O (n) que trate con duplicados.

Entrada: [a1, a2, a3, ...]

Asigne la matriz original como par, donde el primer elemento es un valor y la segunda es el índice de la matriz.

Array: [[a1, i1], [a2, i2], [a3, i3], ...]

Ordene esta matriz de pares con algún algoritmo O (n) (por ejemplo, Ordenamiento de conteo) para ordenar enteros por valor . Obtenemos alguna otra matriz:

Array: [[a3, i3], [a2, i2], [a1, i1], ...]

donde a3, a2, a1, ... están ordenados.

Ejecutar bucle a través de una matriz ordenada de pares

En tiempo lineal podemos detectar grupos consecutivos de números a3, a2, a1. La definición de grupo consecutivo es el siguiente valor = valor anterior + 1. Durante ese escaneo, mantenga el tamaño actual del grupo ( n ), el valor mínimo del índice ( min ) y la suma actual de los índices ( realSum ).

En cada paso dentro de un grupo consecutivo, podemos estimar la suma de los índices, ya que crean una progresión aritmética con el primer elemento min , paso 1 y el tamaño del grupo visto hasta ahora n . Esta estimación de la suma se puede hacer en tiempo O (1) utilizando la fórmula para la progresión aritmética:

suma estimada = (a1 + an) * n / 2;

suma estimada = (min + min + (n - 1)) * n / 2;

suma estimada = min * n + n * (n - 1) / 2;

Si en algún paso del bucle dentro de la suma de la estimación del grupo consecutivo es igual a la suma real, entonces, hasta el momento, el grupo consecutivo cumple las condiciones. Guarde n como resultado máximo actual, o elija el máximo entre el máximo actual y n .

Si en los elementos de valor dejamos de ver el grupo consecutivo, reiniciamos todos los valores y hacemos lo mismo.

Ejemplo de código: https://gist.github.com/mishadoff/5371821

Answer 3

Esta es otra manera de pensar en su problema: suponga que tiene una matriz compuesta solo de 1s y 0s, desea encontrar la carrera consecutiva más larga de 1s. Esto se puede hacer en tiempo lineal mediante la longitud de la ejecución de la codificación de los 1s (ignorar los 0). para transformar su problema original en este nuevo problema de codificación de longitud de ejecución, debe calcular una nueva matriz b [i] = (a [i] <a [i + 1]). Esto no tiene que hacerse explícitamente, solo puede hacerlo de manera implícita para lograr un algoritmo con un requisito de memoria constante y complejidad lineal.

Answer 4

Esto requerirá dos pasadas sobre los datos. Primero crea un mapa hash, mapeando ints a bools. Actualicé mi algoritmo para no usar el mapa, desde el STL, que soy positivo usa la ordenación interna. Este algoritmo utiliza hash y se puede actualizar fácilmente para cualquier combinación máxima o mínima, incluso potencialmente todos los valores posibles que puede obtener un entero.

#include <iostream>

using namespace std;
const int MINIMUM = 0;
const int MAXIMUM = 100;
const unsigned int ARRAY_SIZE = MAXIMUM - MINIMUM;

int main() {

bool* hashOfIntegers = new bool[ARRAY_SIZE];
//const int someArrayOfIntegers[] = {10, 9, 8, 6, 5, 3, 1, 4, 2, 8, 7};
//const int someArrayOfIntegers[] = {10, 6, 5, 3, 1, 4, 2, 8, 7};
const int someArrayOfIntegers[] = {-2, -3, 8, 6, 12, 14,  4, 0, 16, 18, 20};
const int SIZE_OF_ARRAY = 11;

//Initialize hashOfIntegers values to false, probably unnecessary but good practice.
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {
    hashOfIntegers[i] = false;
}

//Chage appropriate values to true.
for(int i = 0; i < SIZE_OF_ARRAY; i++) {
    //We subtract the MINIMUM value to normalize the MINIMUM value to a zero index for negative numbers.
    hashOfIntegers[someArrayOfIntegers[i] - MINIMUM] = true;
}

int sequence = 0;
int maxSequence = 0;
//Find the maximum sequence in the values
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {

    if(hashOfIntegers[i]) sequence++;
    else sequence = 0;

    if(sequence > maxSequence) maxSequence = sequence;
}

cout << "MAX SEQUENCE: " << maxSequence << endl;
return 0;
}

La idea básica es utilizar el mapa hash como una ordenación de depósito, de modo que solo tenga que hacer dos pasadas sobre los datos. Este algoritmo es O (2n), que a su vez es O (n)

Answer 5

No te hagas ilusiones, esta es solo una respuesta parcial.

Estoy bastante seguro de que el problema no es solucionable en O(n) . Desafortunadamente, no puedo probarlo.

Si hay una manera de resolverlo en menos de O(n^2) , sospecho que la solución se basa en la siguiente estrategia:

1. Decida en O(n) (o quizás O(n log n) ) si existe un subarreglo continuo como lo describe con al menos i elementos. Llamemos a este predicado E(i) .
2. Use la bisección para encontrar el máximo i para el cual E(i) cumple.

El tiempo total de ejecución de este algoritmo sería entonces O(n log n) (o O(n log^2 n) ).

Esta es la única forma en que podría llegar para reducir el problema a otro problema que, al menos, tenga el potencial de ser más simple que la formulación original. Sin embargo, no pude encontrar una manera de calcular E(i) en menos de O(n^2) , por lo que puedo estar completamente apagado ...

Answer 6

Vea la matriz S en su definición de conjunto matemático:

S = U _{j = 0} ^k ( I _j )

Donde los I _j son segmentos enteros separados. Puede diseñar un árbol de intervalos específico (basado en un árbol rojo-negro o un árbol de auto-equilibrio que le guste :)) para almacenar la matriz en estas definiciones matemáticas. Las estructuras de los nodos y los árboles deberían verse así:

struct node {
    int d, u;
    int count;
    struct node *n_left, *n_right;
}

Aquí, d es el límite inferior del segmento entero yu, el límite superior. count se agrega para ocuparse de los posibles duplicados en la matriz: al intentar insertar un elemento ya existente en el árbol, en lugar de no hacer nada, incrementaremos el valor de count del nodo en el que se encuentra.

struct root {
    struct node *root;
}        

El árbol solo almacenará nodos separados , por lo tanto, la inserción es un poco más compleja que una inserción de árbol rojo-negro clásico. Al insertar intervalos, debe buscar posibles desbordamientos con intervalos ya existentes. En su caso, ya que solo insertará singletons esto no debería agregar demasiada sobrecarga.

Dados tres nodos P, L y R, siendo L el hijo izquierdo de P y R el hijo derecho de P. Luego, debe imponer Lu <Pd y Pu <Rd (y para cada nodo, d <= u, por supuesto) .

Al insertar un segmento entero [x, y], debe encontrar segmentos "superpuestos", es decir, intervalos [u, d] que satisfagan una de las siguientes desigualdades:

y> = d - 1
O
x <= u + 1

Si el intervalo insertado es un singleton x , entonces solo puede encontrar hasta 2 nodos de intervalo superpuestos N1 y N2, de modo que N1.d == x + 1 y N2.u == x - 1 . Luego, debe combinar los dos intervalos y el recuento de actualizaciones, lo que lo deja con N3, de modo que N3.d = N2.d , N3.u = N1.u y N3.count = N1.count + N2.count + 1 . Dado que el delta entre N1.d y N2.u es el delta mínimo para que dos segmentos se separen, entonces debe tener uno de los siguientes:

• N1 es el hijo adecuado de N2.
• N2 es el hijo izquierdo de N1.

Por lo tanto, la inserción todavía estará en O(log(n)) en el peor de los casos.

Desde aquí, no puedo entender cómo manejar el orden en la secuencia inicial, pero aquí hay un resultado que puede ser interesante: si la matriz de entrada define un segmento entero perfecto , entonces el árbol solo tiene un nodo.

Answer 7

UPD2: La siguiente solución es para un problema cuando no se requiere que el subarray sea contiguo. Entendí mal la declaración del problema. No eliminar esto, ya que alguien puede tener una idea basada en la mía que funcionará para el problema real.

Esto es lo que he encontrado:

Cree una instancia de un diccionario (que se implementa como tabla hash, dando O (1) en situaciones normales). Las claves son enteros, los valores son conjuntos hash de enteros (también O (1)) - var D = new Dictionary<int, HashSet<int>> .

Iterar a través de la matriz A y para cada entero n con índice hago:

1. Compruebe si las claves n-1 y n+1 están contenidas en D
   • si no existe ninguna clave, haga D.Add(n, new HashSet<int>)
   • si solo existe una de las claves, p. ej. n-1 , haga D.Add(n, D[n-1])
   • si existen ambas claves, haga D[n-1].UnionWith(D[n+1]); D[n+1] = D[n] = D[n-1]; D[n-1].UnionWith(D[n+1]); D[n+1] = D[n] = D[n-1];
2. D[n].Add(n)

Ahora pase por cada tecla en D y encuentre el conjunto de hash con la mayor longitud (la longitud de búsqueda es O (1)). La mayor longitud será la respuesta.

A mi entender, la complejidad del caso más desfavorable será O (n * log (n)), solo a causa de la operación UnionWith . No sé cómo calcular la complejidad promedio, pero debería estar cerca de O (n). Por favor, corríjame si estoy equivocado.

UPD: Para hablar de código, aquí hay una implementación de prueba en C # que da el resultado correcto en los dos ejemplos de OP:

var A = new int[] {4, 5, 1, 5, 7, 6, 8, 4, 1};
var D = new Dictionary<int, HashSet<int>>();

foreach(int n in A)
{
    if(D.ContainsKey(n-1) && D.ContainsKey(n+1))
    {
        D[n-1].UnionWith(D[n+1]);
        D[n+1] = D[n] = D[n-1];
    }
    else if(D.ContainsKey(n-1))
    {
        D[n] = D[n-1];
    }
    else if(D.ContainsKey(n+1))
    {
        D[n] = D[n+1];
    }
    else if(!D.ContainsKey(n))
    {
        D.Add(n, new HashSet<int>());
    }

    D[n].Add(n);
}

int result = int.MinValue;
foreach(HashSet<int> H in D.Values)
{
    if(H.Count > result)
    {
        result = H.Count;
    }
}

Console.WriteLine(result);