Second Largest Number

Q: Qual é a complexidade de tempo para encontrar o segundo maior elemento?

Os métodos de uma passagem e de duas passagens levam ambos O(n) de tempo e O(1) de espaço extra. Ordenar primeiro leva O(n log n) de tempo. Não é possível superar O(n) , porque cada valor precisa ser lido pelo menos uma vez.

InicianteArrays e strings

+10

Você recebe uma lista de números inteiros nums. Retorne seu segundo maior valor distinto: o maior valor que é estritamente menor que o máximo. Os valores podem se repetir, então, para [5, 5, 3], a resposta é 3, não 5. A lista sempre contém pelo menos dois valores diferentes.

Função

secondLargest(nums: integer-array) → integer

numsinteger-array: a lista de inteiros, com pelo menos dois valores distintos
Retornainteger: o maior valor que é menor que o máximo

Restrições

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums contém pelo menos dois valores distintos.

Exemplos

Entrada: nums = [4, 9, 2, 7, 9]
Saída: 7
Explicação: O valor máximo é 9. Ele aparece duas vezes, mas uma segunda ocorrência do valor máximo não conta, então a resposta é o próximo valor abaixo, 7.

Entrada: nums = [-5, -1, -8]
Saída: -5
Explicação: Do maior para o menor, os valores são -1, -5, -8. O segundo maior é -5, embora seja negativo.

Entrada: nums = [6, 6, 6, 3]
Saída: 3
Explicação: Existem apenas dois valores distintos, 6 e 3. Não importa quantas vezes 6 se repita, o segundo maior é 3.

+15 testes ocultos ao enviar

Para ir além

Você consegue retornar o terceiro maior valor distinto em uma única passagem, com três variáveis e sem ordenação?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Dois detalhes tornam isso mais difícil do que encontrar o maior valor. O maior valor pode se repetir, e uma repetição não deve ser informada como o segundo maior. A resposta pode ser negativa, então uma variável que começa em 0 dá uma resposta incorreta em uma lista formada apenas por valores negativos. Acompanhar os dois maiores valores distintos em uma única passagem, usando comparações estritas, resolve ambos os casos.

Classifique e desça além do máximo

Intuição

Ordene uma cópia do menor para o maior. O máximo fica no final, possivelmente repetido várias vezes seguidas. Caminhe para a esquerda a partir do final, passando por todas as ocorrências do máximo; o primeiro valor diferente é o segundo maior. Para [6, 6, 6, 3], a cópia ordenada é [3, 6, 6, 6]: você pula três 6s e chega ao 3.

Retornar o penúltimo elemento é o erro clássico aqui. Para [4, 9, 2, 7, 9], isso retorna 9, novamente o máximo. A caminhada não pode ultrapassar o início, porque a lista contém pelo menos dois valores distintos.

A resposta está certa, mas a ordenação organiza todos os valores quando você só se importa com os dois maiores. Ela custa O(n log n) de tempo e a cópia usa O(n) de memória.

Algoritmo

Copie nums e ordene a cópia do menor para o maior.
Comece com o índice i na última posição.
Enquanto o valor em i for igual ao máximo, mova i uma posição para a esquerda.
Retorne o valor em i.

def secondLargest(nums):
    ordered = sorted(nums)
    i = len(ordered) - 1
    # Step left past every copy of the maximum.
    while ordered[i] == ordered[-1]:
        i -= 1
    return ordered[i]

Duas passagens

Intuição

Divida a tarefa em duas etapas. A primeira encontra o máximo, como em Encontrar o maior número. A segunda procura o maior valor que seja estritamente menor que esse máximo. Para [4, 9, 2, 7, 9], a primeira etapa encontra 9, e a segunda ignora ambos os 9 e mantém o maior entre 4, 2 e 7, que é 7.

Inicie second abaixo de qualquer valor que a lista possa conter, como o menor inteiro que sua linguagem oferece. A lista tem pelo menos dois valores distintos, então algum valor é menor que o máximo e sempre substitui esse valor inicial.

Cada etapa calcula um máximo acumulado, então o total é O(n) de tempo e O(1) de espaço. O custo é ler a lista duas vezes, o que é impossível quando os valores chegam um por um e desaparecem depois que você os lê.

Algoritmo

Percorra nums uma vez e armazene o valor máximo em largest.
Defina second como um valor abaixo de todos os valores permitidos.
Percorra novamente. Para cada x com x < largest e x > second, defina second como x.
Retorne second.

def secondLargest(nums):
    largest = nums[0]
    for x in nums:
        if x > largest:
            largest = x
    second = float("-inf")  # below every allowed value
    for x in nums:
        if x < largest and x > second:
            second = x
    return second

Uma passagem acompanhando os dois maiores

Intuição

Mantenha duas variáveis, largest e second, para os dois maiores valores distintos vistos até o momento. Cada novo valor x se enquadra em um de três casos. Se x for maior que largest, o antigo largest passa para o segundo lugar e x assume o primeiro. Se x estiver estritamente entre second e largest, ele se torna o novo second. Em todos os outros casos, nada muda.

As comparações estritas são o que permite lidar com duplicatas. Para [4, 9, 2, 7, 9]: largest se torna 4 e, em seguida, 9, com second = 4. 2 não muda nada; 7 está entre 4 e 9, então second = 7; e o último 9 é igual a largest, portanto é ignorado. A resposta é 7.

Comece ambas as variáveis com valores menores que qualquer valor possível. Começar ambas em 0 retorna 0 para [-5, -1, -8], pois nenhum valor supera 0. Como a lista contém dois valores distintos, second sempre termina com um valor real da lista.

Algoritmo

Defina largest e second abaixo de todos os valores permitidos.
Percorra todos os valores x em nums.
Se x > largest, mova largest para second e defina largest como x.
Caso contrário, se x < largest e x > second, defina second como x.
Após o loop, retorne second.

def secondLargest(nums):
    # Both start below every allowed value.
    largest = second = float("-inf")
    for x in nums:
        if x > largest:
            second = largest  # the old maximum drops to second place
            largest = x
        elif largest > x > second:
            second = x
    return second

Armadilhas e casos extremos

A maioria das respostas erradas ocorre por causa de valores máximos repetidos ou de valores negativos.

Retornar o penúltimo elemento da lista ordenada. Com um valor máximo repetido, como em [4, 9, 2, 7, 9], esse elemento também é o máximo.
Inicializar as variáveis com 0. Em [-5, -1, -8], nenhum valor supera 0, e você retorna 0, um número que não está na lista.
Escrever x >= largest no primeiro caso. Um segundo 9 então coloca o primeiro 9 em second, e você retorna 9.
Atualizar second somente quando aparece um novo máximo. Em [10, 20, 15], o 15 nunca chega a second, e você retorna 10.
Remover as duplicatas com um conjunto e, depois, ordenar. Funciona, mas usa memória O(n) e tempo O(n log n) para uma tarefa que uma única passagem resolve.

Perguntas frequentes4

Como encontrar o segundo maior número em um array em uma única passagem?

Mantenha o maior e o segundo maior valor distinto encontrados até agora. Quando um valor supera o maior, o antigo maior passa para o segundo lugar. Quando um valor fica estritamente entre os dois, ele substitui o segundo. Após uma passagem, a variável do segundo maior contém a resposta.

Qual é a complexidade de tempo para encontrar o segundo maior elemento?

Os métodos de uma passagem e de duas passagens levam ambos O(n) de tempo e O(1) de espaço extra. Ordenar primeiro leva O(n log n) de tempo. Não é possível superar O(n), porque cada valor precisa ser lido pelo menos uma vez.

Como as duplicatas afetam o segundo maior elemento?

Este problema pede o segundo maior valor distinto, então as cópias do valor máximo são ignoradas. Para [9, 9, 7], a resposta é 7. Algumas versões da pergunta contam as posições em vez disso e responderiam 9, então verifique qual interpretação é a pretendida antes de programar.

O que você deve retornar quando não houver um segundo maior valor?

Aqui, isso não pode acontecer: a lista sempre contém dois valores distintos. Em geral, uma lista como [4, 4, 4] não tem resposta, e você retornaria um marcador como -1 ou null, ou geraria um erro. Você pode detectar esse caso quando second ainda mantém seu valor inicial após o loop.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [4, 9, 2, 7, 9]

Esperado

Second Largest Number

Função

Restrições

Exemplos

Dicas

Solução

Classifique e desça além do máximo

Duas passagens

Uma passagem acompanhando os dois maiores

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos