Majority Element

+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 array 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: El 3 aparece tres veces entre cinco elementos. Tres es mayor que 5 / 2 = 2.5, y el 9 y el 4 aparecen una vez cada uno.

+15 pruebas ocultas al enviar

Para ir más allá

¿Puedes encontrar el elemento mayoritario en tiempo O(n) con memoria adicional O(1), sin ordenar el arreglo?

Solución

Contar cuántas veces aparece cada valor responde a la pregunta, pero los recuentos necesitan un mapa hash. Para descartarlo, hay que ver qué hace especial al valor mayoritario: aparece más veces que todos los demás valores juntos. Empareja cada copia de este valor con un valor diferente y tacha ambos; siempre quedan algunas copias. La votación de Boyer-Moore realiza esos emparejamientos en una sola pasada con un candidato y un contador.

Cuenta con un mapa hash

Intuición

Recorre el arreglo y mantén un mapa hash que asocie cada valor con el número de veces que lo has visto. Después de sumar uno al contador de un valor, comprueba si ese contador ahora es mayor que la mitad de la longitud. El primer valor que supere ese límite es la mayoría, así que puedes devolverlo de inmediato.

Para [3, 9, 3, 3, 4], el contador de 3 pasa a ser 1 en el índice 0, 2 en el índice 2 y 3 en el índice 3. Tres apariciones de un total de cinco es más que 2.5, así que devuelves 3 sin leer el último elemento.

Una búsqueda y una actualización en un mapa hash toman O(1) en promedio, así que el tiempo es O(n). El mapa puede contener hasta aproximadamente n / 2 valores diferentes, así que la memoria adicional es O(n). El siguiente enfoque prescinde del mapa.

Algoritmo

Crea un mapa vacío de valores a cantidades.
Para cada elemento x, suma 1 a la cantidad de x.
Si esa cantidad multiplicada 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

Trata el array como una elección. Conserva un candidate y un count de sus votos que aún no se han cancelado. Un elemento igual al candidato suma un voto. Un elemento distinto cancela un voto, y ambos abandonan juntos la contienda. Cuando el contador es 0, el siguiente elemento se convierte en el nuevo candidato.

Por qué el valor que queda al final es la mayoría: cada cancelación elimina dos valores distintos, así que elimina como máximo una copia de la mayoría. Supongamos que la mayoría aparece m veces. Solo hay n - m elementos diferentes, menos que m, así que no pueden cancelar todas las copias. Todos los votos que siguen en pie al final pertenecen al candidato final, y entre ellos hay una copia de la mayoría, así que el candidato es la mayoría.

En [8, 8, 1, 1, 8, 1, 8], el contador pasa por 1, 2, 1, 0: los dos 1 han cancelado ambos 8. El siguiente 8 vuelve a empezar con un contador de 1, el siguiente 1 lo cancela y el último 8 vuelve a convertirse en el candidato. Devuelves 8. Una pasada con dos variables requiere tiempo O(n) y memoria O(1).

Algoritmo

Establece candidate en 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

La mayoría de las respuestas incorrectas se deben a confundir el límite de la mitad o a interpretar demasiado el contador.

«Más de la mitad» es una condición estricta. count >= n / 2 acepta 2 copias de 4, lo cual no es una mayoría. Compara count * 2 > n y ningún redondeo podrá interferir.
El count final en Boyer-Moore no indica cuántas veces aparece el 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 funciona solo si el bucle empieza después en el índice 1. Si empieza en el índice 0, el primer elemento vota dos veces: con [1, 2, 2], el contador termina en 0 y devuelves 1.
Boyer-Moore se basa en la garantía. Con [1, 2, 3], que no tiene mayoría, igualmente devuelve 3. Si es posible que una entrada no tenga mayoría, cuenta el candidato en una segunda pasada antes de confiar en él.

Preguntas frecuentes4

¿Qué es el algoritmo de votación de Boyer-Moore?

Encuentra el valor que aparece en más de la mitad de una lista en una sola pasada con memoria O(1). Mantiene un candidato y un contador: un elemento coincidente suma uno, un elemento diferente resta uno y, cuando llega a 0, el siguiente elemento se convierte en el candidato. Como el valor mayoritario supera en cantidad a todos los demás valores combinados, es el candidato que queda al final.

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

La votación de Boyer-Moore se ejecuta en tiempo O(n) y usa O(1) de espacio adicional. 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 quedan en un 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. Es breve de escribir, pero cuesta O(n log n) de tiempo.

¿Qué pasa si el array podría no tener un elemento mayoritario?

Boyer-Moore siempre devuelve algún candidato, incluso cuando ningún valor aparece en más de la mitad del arreglo. Agrega una segunda pasada que cuente el candidato y acéptalo solo si el recuento es mayor que n / 2. El total se mantiene en O(n) de tiempo y O(1) de espacio.

Python

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

Casos de prueba

Caso 1

Caso 2

Entrada

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

Esperado