Majority Element

+10

Você recebe um array de números inteiros nums de comprimento n. Um valor aparece nele mais de n / 2 vezes, e esse valor é chamado de elemento majoritário. Retorne-o. Um valor que ocupa mais da metade do array é sempre único, então há exatamente uma resposta.

Função

majorityElement(nums: integer-array) → integer

numsinteger-array: o array de inteiros, com um valor ocupando mais da metade dele
Retornainteger: o valor que aparece mais de n / 2 vezes

Restrições

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Um valor aparece mais de nums.length / 2 vezes.

Exemplos

Entrada: nums = [3, 9, 3, 3, 4]
Saída: 3
Explicação: 3 aparece três vezes em cinco elementos. Três é maior que 5 / 2 = 2.5, e 9 e 4 aparecem uma vez cada.

+15 testes ocultos ao enviar

Para ir além

Você consegue encontrar o elemento majoritário em O(n) de tempo, usando O(1) de memória extra, sem ordenar o array?

Solução

Contar quantas vezes cada valor aparece responde à pergunta, mas as contagens exigem um mapa hash. Para dispensá-lo, basta observar o que torna o valor majoritário especial: ele aparece mais vezes do que todos os outros valores juntos. Emparelhe cada ocorrência dele com um valor diferente e risque ambos; algumas ocorrências sempre sobrarão. O algoritmo de votação de Boyer-Moore faz esse emparelhamento em uma única passagem, usando um candidato e um contador.

Conte com um mapa hash

Intuição

Percorra o array e mantenha um mapa hash que associe cada valor ao número de vezes que você o encontrou. Depois de adicionar um ao contador de um valor, verifique se esse contador agora é maior que a metade do comprimento. O primeiro valor a ultrapassar esse limite é a maioria, então você pode retorná-lo imediatamente.

Para [3, 9, 3, 3, 4], a contagem de 3 passa a ser 1 no índice 0, 2 no índice 2 e 3 no índice 3. Três ocorrências em cinco é mais que 2.5, então você retorna 3 sem ler o último elemento.

Uma consulta e uma atualização no mapa hash levam O(1) em média, então o tempo é O(n). O mapa pode armazenar até cerca de n / 2 valores diferentes, então a memória extra é O(n). A próxima abordagem elimina o mapa.

Algoritmo

Crie um mapa vazio de valores para contagens.
Para cada elemento x, adicione 1 à contagem de x.
Se essa contagem multiplicada por 2 for maior que o comprimento do array, retorne x.

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

Votação de Boyer-Moore

Intuição

Trate o array como uma eleição. Mantenha um candidate e uma count dos votos dele que ainda não foram cancelados. Um elemento igual ao candidato acrescenta um voto. Um elemento diferente cancela um voto, e os dois saem juntos da disputa. Quando a contagem é 0, o próximo elemento se torna o novo candidato.

Por que o valor que resta no final é a maioria: cada cancelamento remove dois valores diferentes, então remove no máximo uma cópia da maioria. Digamos que a maioria apareça m vezes. Há apenas n - m outros elementos, menos que m, então eles não podem cancelar todas as cópias. Todos os votos que permanecem no final pertencem ao candidato final, e uma cópia da maioria está entre eles, portanto o candidato é a maioria.

Em [8, 8, 1, 1, 8, 1, 8], a contagem vai de 1 a 2, depois 1 e 0: os dois 1s cancelaram ambos os 8s. O próximo 8 recomeça com uma contagem de 1, o próximo 1 o cancela, e o último 8 se torna o candidato novamente. Você retorna 8. Uma passagem com duas variáveis leva O(n) de tempo e O(1) de memória.

Algoritmo

Defina candidate como o primeiro elemento e count como 0.
Para cada elemento x, se count for 0, defina x como candidato.
Se x for igual ao candidato, some 1 a count. Caso contrário, subtraia 1.
Após o último elemento, retorne 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

Armadilhas e casos extremos

A maioria das respostas erradas vem da linha da metade ou de interpretar demais o contador.

“Mais da metade” é estrito. count >= n / 2 aceita 2 ocorrências em 4, o que não é maioria. Compare count * 2 > n e nenhum arredondamento poderá atrapalhar.
O count final do Boyer-Moore não indica quantas vezes a maioria aparece. Para [8, 8, 1, 1, 8, 1, 8], ele termina em 1, enquanto 8 aparece quatro vezes.
Começar com candidate = nums[0] e count = 1 funciona apenas se o loop começar no índice 1. Comece no índice 0 e o primeiro elemento votará duas vezes: em [1, 2, 2], a contagem termina em 0 e você retorna 1.
O Boyer-Moore depende da garantia. Em [1, 2, 3], que não tem maioria, ele ainda retorna 3. Se uma entrada puder não ter maioria, conte o candidato em uma segunda passagem antes de confiar nele.

Perguntas frequentes4

O que é o algoritmo de votação de Boyer-Moore?

Ele encontra o valor que aparece em mais da metade de uma lista em uma única passagem, usando memória O(1). Ele mantém um candidato e um contador: um elemento correspondente adiciona um, um elemento diferente subtrai um e, quando chega a 0, o próximo elemento se torna o candidato. Como o valor majoritário aparece mais vezes do que todos os outros valores juntos, ele é o candidato que resta no final.

Qual é a complexidade de tempo e espaço do Elemento Majoritário?

A votação de Boyer-Moore é executada em tempo O(n) e usa O(1) de espaço extra. A contagem com um mapa hash também leva tempo O(n), mas precisa de O(n) de espaço para as contagens. Ordenar primeiro leva tempo O(n log n).

É possível resolver o problema do Elemento Majoritário usando ordenação?

Sim. Após a ordenação, todas as cópias do elemento majoritário ficam em um único bloco com mais da metade do tamanho do array, e qualquer bloco assim contém a posição central. Portanto, o elemento no índice n / 2, arredondado para baixo, é a resposta. É curto de escrever, mas custa O(n log n) de tempo.

E se o array não tiver um elemento majoritário?

Boyer-Moore sempre retorna algum candidato, mesmo quando nenhum valor ocupa mais da metade do array. Adicione uma segunda passagem que conte o candidato e aceite-o somente se a contagem for maior que n / 2. O total continua sendo O(n) de tempo e O(1) de espaço.

Python

def majorityElement(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

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

Esperado