Majority Element

Q: ¿Y si el array no tuviera un elemento mayoritario?

Boyer-Moore siempre devuelve algún candidato: en [1, 2, 3] devuelve 3. Añade una segunda pasada que cuente el candidato y acéptalo solo si el recuento es mayor que n / 2 . El total sigue siendo O(n) de tiempo y O(1) de espacio.

FácilHashing

+10

Recibes un arreglo de enteros nums de longitud n. Un valor aparece en él más de n / 2 veces, y ese valor se llama elemento mayoritario. Devuélvelo. Un valor que ocupa más de la mitad del arreglo siempre es único, así que hay exactamente una respuesta.

Función

majorityElement(nums: integer-array) → integer

numsinteger-array: el arreglo de enteros, con un valor que ocupa más de la mitad
Devuelveinteger: el valor que aparece más de n / 2 veces

Restricciones

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Un valor aparece más de nums.length / 2 veces.

Ejemplos

Entrada: nums = [3, 9, 3, 3, 4]
Salida: 3
Explicación: 3 aparece tres veces en cinco elementos. Tres es más que 5 / 2 = 2.5, y 9 y 4 aparecen una vez cada uno.

Para ir más allá

¿Puedes encontrar todos los valores que aparecen más de n / 3 veces, en tiempo O(n) y con memoria adicional O(1)?

Solución

La mayoría supera en número a todos los demás valores juntos. Tacha pares de valores distintos y algunas de sus copias siempre sobreviven. La votación de Boyer-Moore realiza ese emparejamiento en una sola pasada con un candidato y un contador, así que no necesitas un mapa hash de frecuencias.

Cuenta con un mapa hash

Intuición

Cuenta cada valor en un mapa hash y devuelve el primer valor cuyo recuento supere la mitad de la longitud. Para [3, 9, 3, 3, 4], el recuento de 3 llega a 3 en el índice 3, más de 2.5, así que lo devuelves antes de leer el 4.

En promedio, cada búsqueda es O(1), por lo que el tiempo es O(n), pero el mapa puede contener aproximadamente n / 2 valores diferentes: memoria O(n).

Algoritmo

Crea un mapa vacío de valores a recuentos.
Para cada elemento x, suma 1 al recuento de x.
Si ese recuento multiplicado por 2 es mayor que la longitud del arreglo, devuelve x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Votación de Boyer-Moore

Intuición

Mantén un candidate y un count de sus votos que aún no se han cancelado. Un elemento igual al candidato suma un voto. Uno diferente cancela un voto, y ambos salen de la contienda. Cuando el conteo llega a 0, el siguiente elemento se convierte en el candidato.

Cada cancelación elimina dos valores diferentes, así que como máximo una copia del elemento mayoritario. Si el elemento mayoritario aparece m veces, los otros n - m elementos son menos de m y no pueden cancelar todas sus copias. Todos los votos que quedan al final pertenecen al candidato final, y entre ellos hay una copia del elemento mayoritario.

Con [8, 8, 1, 1, 8, 1, 8], el conteo pasa por 1, 2, 1, 0 a medida que los 1 cancelan ambos 8. El siguiente 8 reinicia el conteo en 1, el siguiente 1 lo cancela y el último 8 vuelve a convertirse en el candidato. Un recorrido con dos variables requiere O(n) tiempo y O(1) memoria.

Algoritmo

Establece candidate como el primer elemento y count en 0.
Para cada elemento x, si count es 0, convierte x en el candidato.
Si x es igual al candidato, suma 1 a count. De lo contrario, resta 1.
Después del último elemento, devuelve candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

Errores comunes y casos límite

"Más de la mitad" es estricto. count >= n / 2 acepta 2 copias de 4, lo cual no es una mayoría. Compara count * 2 > n y ningún redondeo interfiere.
Interpretar el count final como la frecuencia del elemento mayoritario. Para [8, 8, 1, 1, 8, 1, 8] termina en 1, mientras que 8 aparece cuatro veces.
Empezar con candidate = nums[0] y count = 1, y después recorrer desde el índice 0. El primer elemento vota dos veces: con [1, 2, 2], el recuento termina en 0 y devuelves 1.

Preguntas frecuentes3

¿Cuál es la complejidad temporal y espacial del elemento mayoritario?

La votación de Boyer-Moore se ejecuta en tiempo O(n) y espacio adicional O(1). Contar con un mapa hash también requiere tiempo O(n), pero necesita espacio O(n) para los conteos. Ordenar primero requiere tiempo O(n log n).

¿Se puede resolver el problema del elemento mayoritario ordenando?

Sí. Después de ordenar, todas las copias del elemento mayoritario se encuentran en un único bloque de longitud superior a la mitad del arreglo, y cualquier bloque así abarca la posición central. Por lo tanto, el elemento en el índice n / 2, redondeado hacia abajo, es la respuesta, con un costo de tiempo de O(n log n).

¿Y si el array no tuviera un elemento mayoritario?

Boyer-Moore siempre devuelve algún candidato: en [1, 2, 3] devuelve 3. Añade una segunda pasada que cuente el candidato y acéptalo solo si el recuento es mayor que n / 2. El total sigue siendo O(n) de tiempo y O(1) de espacio.

def majorityElement(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

nums = [3, 9, 3, 3, 4]

Salida Esperada