arrays algorithm

arrays - Encuentra la subarray más larga que contiene un elemento mayoritario.



algorithm (4)

Esto explica y explica cómo funciona el intento 2 en la solución @PhamTrung

Para obtener la longitud del subarray más largo. Deberíamos

  1. Encuentra el máximo. número de elemento mayoritario en una matriz válida, denota como m
    • Esto se hace intentando 2 en la solución @PhamTrung
  2. Retorno min (2 * m -1, longitud de la matriz dada)

Concepto

El intento se deriva de un método para resolver el subconjunto positivo más largo

Mantenemos una matriz de contador para cada número único x . Hacemos un +1 cuando encontramos x . De lo contrario, haz un -1 .

Tomar matriz [0,1,2,0,0,3,4,5,0,0,1,0] y número único 0 , tenemos matriz contador [1,0, -1,0,1,0, -1, -2, -1,0, -1,0]. Si cegamos los que no son números únicos de destino, obtenemos [1, #, #, 0,1, #, #, #, - 1,0, #, 0].

Podemos obtener una matriz válida de la matriz de contador ciego cuando existen dos contadores de tal manera que el valor del contador derecho sea mayor o igual al de la izquierda. Ver la parte de prueba.

Para mejorarlo aún más, podemos ignorar todos los # ya que son inútiles y obtenemos [1 (0), 0 (3), 1 (4), - 1 (8), 0 (9), 0 (11)] en Formato de cuenta (índice).

Podemos mejorar esto aún más al no registrar un contador que sea mayor que su contador efectivo anterior. Tome el contador del índice 8,9 como ejemplo, si puede formar un subarray con el índice 9, entonces debe poder formar un subarray con el índice 8. Entonces, solo necesitamos [1 (0), 0 (3), - 1 (8)] para computación.

Puede formar un subarreglo válido con el índice actual con todos los índices anteriores utilizando la búsqueda binaria en la matriz del contador buscando el valor más cercano que sea menor o igual al valor del contador actual (si se encuentra)

Prueba

Cuando el contador derecho es mayor que el contador izquierdo por r para un x particular, donde k, r> = 0, debe haber k + r número de xyk el número de no x existe después del contador izquierdo. Así

  1. Los dos contadores están en la posición de índice i y r + 2k + i
  2. La forma del subarreglo entre [i, r + 2k + i] tiene exactamente k + r + 1 número de x
  3. La longitud del subarreglo es 2k + r + 1.
  4. El subarreglo es válido como ( 2k + r + 1 ) <= 2 * ( k + r + 1 ) -1

Procedimiento

  1. Sea m = 1
  2. Corta la matriz de izquierda a derecha
  3. Para cada índice p i
    • Si el número es el primer encuentro,
      1. Crear una nueva matriz de contador [1 (p i )]
      2. Cree un nuevo registro de índice que almacene el valor actual del índice (p i ) y el valor del contador (1)
    • De lo contrario, reutilice la matriz de contador y la matriz de índice del número y realice
      1. Calcule el valor del contador actual c i por c prev + 2- (p i - p prev ), donde c prev , p prev son el valor del contador y el índice en el registro de índice
      2. Realice una búsqueda binaria para encontrar el subarreglo más largo que se puede formar con la posición actual del índice y toda la posición anterior del índice. es decir, encuentre la c más cercana, c la más cercana , en la matriz del contador donde c <= c i . Si no se encuentra, salta al paso 5

      3. Calcule el número de x en el subarreglo que se encuentra en el paso 2

        r = c i - c más cercano

        k = (p i -p más cercano -r) / 2

        número de x = k + r + 1

      4. Actualice el contador m por el número de x si el subarray tiene el número de x > m
      5. Actualice la matriz del contador agregando el contador actual si el valor del contador es menor que el último valor del contador registrado
      6. Actualizar el registro de índice por el índice actual (p i ) y el valor del contador (c i )

Estoy tratando de resolver este problema algorítmico:

https://dunjudge.me/analysis/problems/469/

Para mayor comodidad, he resumido la declaración del problema a continuación.

Dada una matriz de longitud (<= 2,000,000) que contiene enteros en el rango [0, 1,000,000], encuentre la subarray más larga que contenga un elemento mayoritario.

Un elemento mayoritario se define como un elemento que aparece> piso (n / 2) veces en una lista de longitud n.

Límite de tiempo: 1.5s

Por ejemplo:

Si la matriz dada es [1, 2, 1, 2, 3, 2],

La respuesta es 5 porque el subarreglo [2, 1, 2, 3, 2] de longitud 5 desde la posición 1 a 5 (0 indexado) tiene el número 2 que aparece 3> piso (5/2) veces. Tenga en cuenta que no podemos tomar toda la matriz porque 3 = piso (6/2).

Mi intento:

Lo primero que viene a la mente es una solución obvia de fuerza bruta (pero correcta) que corrige los índices de inicio y fin de un subarreglo y un bucle a través de él para verificar si contiene un elemento mayoritario. Luego tomamos la longitud del subarreglo más largo que contiene un elemento mayoritario. Esto funciona en O (n ^ 2) con una pequeña optimización. Claramente, esto no pasará el límite de tiempo.

También estaba pensando en dividir los elementos en grupos que contienen sus índices en orden ordenado.

Usando el ejemplo anterior, estos cubos serían:

1: 0, 2

2: 1, 3, 5

3: 4

Luego, para cada grupo, intentaría fusionar los índices para encontrar el subarreglo más largo que contenga k como el elemento mayoritario, donde k es la etiqueta del número entero de ese grupo. Entonces podríamos tomar la longitud máxima sobre todos los valores de k. No probé esta solución porque no sabía cómo realizar el paso de fusión.

¿Podría alguien, por favor, aconsejarme un mejor enfoque para resolver este problema?

Editar:

Resolví este problema gracias a las respuestas de PhamTrung y hk6279. Aunque acepté la respuesta de PhamTrung porque él sugirió la idea por primera vez, recomiendo encarecidamente buscar la respuesta en hk6279 porque su respuesta elabora la idea de PhamTrung y es mucho más detallada (¡y también viene con una buena prueba formal!).

Nota: el intento 1 es incorrecto ya que @ hk6279 ha dado un ejemplo de contador. Gracias por mencionarlo.

Intento 1: la respuesta es bastante compleja, por lo que discutiré una breve idea

Vamos a procesar cada número único uno por uno.

Al procesar cada aparición del número x de izquierda a derecha, en el índice i , permita que se agregue un segmento (i, i) indica el inicio y el final del subarreglo actual. Después de eso, debemos mirar hacia el lado izquierdo de este segmento, e intentar fusionar el vecino izquierdo de este segmento en (i, i) , (Entonces, si la izquierda es (st, ed) , tratamos de hacerlo conviértase (st, i) si satisface la condición) si es posible, y continúe fusionándolos hasta que no podamos fusionarnos, o no quede ningún vecino.

Mantenemos todos esos segmentos en una pila para una búsqueda / adición / eliminación más rápida.

Finalmente, para cada segmento, tratamos de ampliarlos lo más grande posible y mantener el mayor resultado.

La complejidad del tiempo debe ser O(n) ya que cada elemento solo se podría fusionar una vez.

Intento 2 :

Vamos a procesar cada número único uno por uno

Para cada número único x , mantenemos una matriz de contador. Desde 0 hasta el final de la matriz, si encontramos un valor x aumentamos el conteo, y si no lo hacemos disminuimos, entonces para esta matriz [0,1,2,0,0,3,4,5,0 , 0] y el número 0 , tenemos este contador matriz

[1,0, -1,0,1,0, -1, -2, -1,0]

Por lo tanto, para hacer un subarreglo válido que termine en un índice específico i , el valor del counter[i] - counter[start - 1] debe ser mayor que 0 (Esto puede explicarse fácilmente si ve la matriz como una marca de 1 y -1 entradas; con 1 is when there is an occurrence of x, -1 otherwise , y el problema se puede convertir para encontrar el subarray con suma positiva)

Entonces, con la ayuda de una búsqueda binaria, los elementos anteriores aún tienen una complejidad de O (n ^ 2 log n) (en caso de que tengamos n / 2 números únicos, debemos hacer el proceso anterior n / 2 veces, cada uno tiempo toma O (n log n))

Para mejorarlo, observamos que en realidad no necesitamos almacenar todos los valores para todos los contadores, sino solo los valores de contador de x , vimos que podemos almacenar para el contador de matriz anterior:

[1, #, #, 0,1, #, #, #, - 1,0]

Esto llevará a la solución O (n log n), que solo pasa por cada elemento una vez.

Para completar, aquí hay un resumen de una teoría O(n) . Considere lo siguiente, donde * son caracteres diferentes de c :

* c * * c * * c c c i: 0 1 2 3 4 5 6 7 8 9

Un gráfico para sumar 1 para c y restar 1 para un carácter distinto de c podría tener este aspecto:

sum_sequence 0 c c -1 * * c c -2 * * c -3 *

Una gráfica para el mínimo de la secuencia de suma anterior, vista para c , podría verse como:

min_sum 0 c * * -1 * c * * -2 c c c

Claramente, para cada aparición de c , estamos buscando la aparición más a la izquierda de c con sum_sequence inferior o igual a la sum_sequence actual. Una diferencia no negativa significaría que c es una mayoría, y el extremo izquierdo garantiza que el intervalo es el más largo hasta nuestra posición. (Podemos extrapolar una longitud máxima que está delimitada por caracteres distintos de c de los límites internos de c ya que el primero puede ser flexible sin afectar a la mayoría).

Observe que de una ocurrencia de c a la siguiente, su sum_sequence puede disminuir en un tamaño arbitrario. Sin embargo, solo puede aumentar en 1 entre dos apariciones consecutivas de c . En lugar de cada valor de min_sum para c , podemos registrar segmentos lineales, marcados por las ocurrencias de c s. Un ejemplo visual:

[start_min / / / / end_min, start_min / / end_min]

Repetimos las incidencias de c y mantenemos un puntero al segmento óptimo de min_sum . Claramente podemos derivar el siguiente valor de sum_sequence para c del anterior, ya que está disminuido exactamente por el número de caracteres intermedios.

Un aumento en la sum_sequence de la sum_sequence para c corresponde con un desplazamiento de 1 atrás o ningún cambio en el puntero al segmento de min_sum óptimo. Si no hay ningún cambio en el puntero, el valor de sum_sequence actual es una clave para el valor del puntero actual. Puede haber O(num_occurrences_of_c) tales claves hash.

Con una disminución arbitraria en el valor de sum_sequence c , ya sea (1) sum_sequence es más bajo que el segmento min_sum más min_sum registrado, así que agregamos un nuevo segmento más bajo y actualizamos el puntero, o (2) hemos visto este valor exacto de sum_sequence antes (ya que todos los aumentos son solo por 1 ) y puede utilizar nuestro hash para recuperar el segmento de min_sum óptimo en O(1) .

Como Matt Timmermans señaló en los comentarios de la pregunta, si tuviéramos que actualizar continuamente el puntero al min_sum de iteración iterando sobre la lista, seguiríamos realizando solo O(1) iteraciones de tiempo amortizado por ocurrencia de caracteres. Vemos que para cada segmento creciente de sum_sequence de sum_sequence , podemos actualizar el puntero en O(1) . Si utilizamos la búsqueda binaria solo para los descensos, agregaríamos como máximo (log k) iteraciones para cada k ocurrencias (esto supone que saltamos todo el camino), lo que mantiene nuestro tiempo total en O(n) .

Algoritmo : Esencialmente, lo que hace Boyer-Moore es buscar un sufijo sufsuf de números donde suf [0] suf [0] es el elemento mayoritario en ese sufijo. Para hacer esto, mantenemos un recuento, que se incrementa cada vez que vemos una instancia de nuestro candidato actual para el elemento de mayoría y decrementa cuando vemos algo más. Cuando el recuento es igual a 0, efectivamente olvidamos todo en números hasta el índice actual y consideramos el número actual como el candidato para el elemento mayoritario. No es inmediatamente obvio por qué podemos olvidarnos de olvidar los prefijos de números. Considere los siguientes ejemplos (las tuberías se insertan para separar las ejecuciones del conteo distinto de cero).

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

Aquí, el 7 en el índice 0 se selecciona para ser el primer candidato para el elemento mayoritario. el conteo finalmente llegará a 0 después de que se procese el índice 5, por lo que el 5 en el índice 6 será el próximo candidato. En este caso, 7 es el verdadero elemento de la mayoría, por lo que al ignorar este prefijo, ignoramos un número igual de elementos mayoritarios y minoritarios; por lo tanto, 7 seguirá siendo el elemento de la mayoría en el sufijo formado al desechar el primer prefijo.

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

Ahora, el elemento mayoritario es 5 (cambiamos la última ejecución de la matriz de 7s a 5s), pero nuestro primer candidato sigue siendo 7. En este caso, nuestro candidato no es el elemento mayoritario verdadero, pero aún no podemos descartar más mayoría elementos que elementos minoritarios (esto implicaría que el recuento podría alcanzar -1 antes de que reasignemos el candidato, lo que obviamente es falso).

Por lo tanto, dado que es imposible (en ambos casos) descartar más elementos mayoritarios que minoritarios, estamos seguros de descartar el prefijo e intentar resolver recursivamente el problema del elemento mayoritario para el sufijo. Eventualmente, se encontrará un sufijo para el cual el conteo no llega a 0, y el elemento mayoritario de ese sufijo será necesariamente el mismo que el elemento mayoritario de la matriz general.

Aquí está la solución de Java:

  • Complejidad del tiempo: O (n)

  • Complejidad del espacio: O (1)

    public int majorityElement(int[] nums) { int count = 0; Integer candidate = null; for (int num : nums) { if (count == 0) { candidate = num; } count += (num == candidate) ? 1 : -1; } return candidate; }