Find the Largest Number

Q: Qual é a complexidade de tempo para encontrar o valor máximo em um array?

Uma passagem leva tempo O(n) e usa espaço extra O(1) . Nenhum método aplicado a um array não ordenado pode ser melhor, porque qualquer elemento que você não ler pode ser o maior. Ordenar primeiro custa O(n log n) , o que é mais lento sem trazer nenhum benefício.

InicianteArrays e strings

+10

Você recebe uma lista não vazia de números inteiros nums. Retorne o maior valor nela. Os valores podem ser negativos, então a resposta também pode ser negativa. Encontre-o com suas próprias comparações, sem uma função de máximo integrada, como max.

Função

findMax(nums: integer-array) → integer

numsinteger-array: a lista de números inteiros a pesquisar
Retornainteger: o maior valor em nums

Restrições

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Exemplos

Entrada: nums = [3, 17, 4, 12, 9]
Saída: 17
Explicação: Lendo da esquerda para a direita, o maior valor até agora é 3, depois 17. Nenhum de 4, 12 ou 9 supera 17, então a resposta é 17.

Entrada: nums = [-8, -3, -11, -3]
Saída: -3
Explicação: Todos os valores são negativos, e -3 é o mais próximo de zero, portanto é o maior. Ele aparece duas vezes, mas você retorna o valor, não a posição dele.

+13 testes ocultos ao enviar

Para ir além

Você consegue retornar tanto o maior quanto o menor valor com cerca de 3n/2 comparações, em vez de 2n, comparando primeiro os valores em pares?

Dicas

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

0 de 3 abertas

Solução

Qualquer valor que você ignorar pode ser o maior, então toda solução lê cada elemento pelo menos uma vez. A única decisão real é onde começa o máximo atual. Comece pelo primeiro elemento, nunca por 0, porque todos os valores da lista podem ser negativos.

Ordene uma cópia e obtenha o último valor

Intuição

Em uma lista ordenada do menor para o maior, o maior valor fica no final. Copie nums para manter a lista de quem chamou a função como estava, ordene a cópia e retorne seu último elemento. Para [3, 17, 4, 12, 9], a cópia ordenada é [3, 4, 9, 12, 17], e o último elemento é 17.

A resposta está correta, mas ordenar faz muito mais do que você precisa. Isso coloca todos os valores em ordem, o que exige cerca de n log n comparações, aproximadamente 60,000 para n = 5000, quando você quer apenas o maior. A cópia também custa O(n) de memória.

Em JavaScript e TypeScript, passe um comparador para sort. Sem um comparador, os números são comparados como texto, o que coloca 12 e 17 antes de 3.

Algoritmo

Copie nums.
Ordene a cópia do menor para o maior, comparando os números como números.
Retorne o último elemento da cópia ordenada.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

Uma passagem com um máximo acumulado

Intuição

Mantenha uma variável, largest, para armazenar o maior valor encontrado até então. Comece com nums[0], compare-o com cada valor e substitua-o sempre que um valor for maior. Quando o loop terminar, largest terá sido comparado com todos os elementos, então nenhum valor da lista será maior que ele.

Para [3, 17, 4, 12, 9], largest começa com 3, passa a ser 17 e continua sendo 17 com 4, 12 e 9. São n-1 comparações úteis e uma variável extra.

Começar com nums[0] é o que faz listas com números negativos funcionarem. Se começar com 0, [-8, -3, -11, -3] nunca terá um valor maior que ele, então você retornará 0, um valor que nem sequer está na lista.

Algoritmo

Defina largest como nums[0].
Percorra todos os valores x em nums.
Se x > largest, defina largest como x.
Após o loop, retorne largest.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

Armadilhas e casos extremos

O loop é curto, então os erros estão em onde ele começa e no que lê.

Começar largest com 0 ou -1. Qualquer lista cujos valores sejam todos menores que esse valor inicial retorna um número que não está na lista.
Começar com um número pequeno inventado, como -1000000. Os valores aqui chegam a -10^9, então o valor inicial ainda prevalece. nums[0] não exige nenhum palpite.
Ler nums[0] em Lua ou R, onde o primeiro elemento é nums[1]. Lua retorna nil e R retorna um vetor vazio.
Fazer um loop com i ≤ n em uma linguagem com índices baseados em 0, o que lê um elemento além do fim.
Ordenar sem um comparador numérico em JavaScript ou TypeScript. A ordem textual de [3, 17, 4, 12, 9] termina com 9, então você retorna 9 em vez de 17.

Perguntas frequentes4

Qual é a complexidade de tempo para encontrar o valor máximo em um array?

Uma passagem leva tempo O(n) e usa espaço extra O(1). Nenhum método aplicado a um array não ordenado pode ser melhor, porque qualquer elemento que você não ler pode ser o maior. Ordenar primeiro custa O(n log n), o que é mais lento sem trazer nenhum benefício.

Como encontrar o maior número em um array sem usar max?

Armazene o primeiro elemento em uma variável. Percorra os demais e, sempre que um elemento for maior que a variável, armazene esse elemento no lugar. Quando o loop terminar, a variável conterá o maior valor.

Por que o máximo acumulado deve começar no primeiro elemento e não em 0?

Se todos os valores forem negativos, nenhum deles será maior que 0, então um máximo que começa em 0 nunca muda e a função retorna 0. O primeiro elemento é sempre um candidato válido, então começar por ele é correto para qualquer lista. O menor inteiro da sua linguagem também funciona, desde que a lista nunca esteja vazia.

Quando a ordenação é uma boa maneira de encontrar o maior valor?

Quando você precisa de mais do que o maior valor, como os três maiores valores ou a mediana, e vai fazer muitas perguntas desse tipo sobre a mesma lista. Para obter apenas o valor máximo, uma única passagem é mais rápida e não altera a lista.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado