Check if an Array Is Sorted
Você recebe um array de números inteiros nums. Retorne true se ele estiver em ordem não decrescente, ou seja, se cada elemento for menor ou igual ao próximo, e false caso contrário. Elementos vizinhos iguais são permitidos: [2, 2, 3] é considerado ordenado. Um array com um único elemento está ordenado.
Função
- numsinteger-array
- o array de números inteiros a ser verificado
- Retornaboolean
- true quando cada elemento é menor ou igual ao próximo; caso contrário, false
Restrições
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Exemplos
- Entrada
- nums = [1, 3, 3, 7]
- Saída
- true
- Explicação
- Cada etapa sobe ou permanece no mesmo nível: de 1 para 3, de 3 para 3, de 3 para 7. O 3 repetido é permitido, então a resposta é
true.
- Entrada
- nums = [2, 5, 4, 9]
- Saída
- false
- Explicação
- A passagem de 5 para 4 é decrescente. Uma única passagem assim basta para deixar o array fora de ordem, embora 9 no final seja o maior valor; portanto, a resposta é
false.
Para ir além
Como você verificaria, em uma única passagem, se um array pode estar ordenado em qualquer uma das direções, crescente ou decrescente?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Se um array não estiver ordenado, onde você pode ver isso nele? Você precisa comparar elementos que estão distantes?
Basta comparar cada elemento com o que vem logo depois dele. Elementos vizinhos iguais são permitidos; apenas uma queda interrompe a ordem.
Percorra os pares vizinhos e retorne
falseno primeiro par em que o valor à esquerda for maior que o da direita. Se não houver nenhum par assim, retornetrue.
Solução
Um array está ordenado exatamente quando nenhum elemento é maior que o elemento logo depois dele. Você nunca precisa comparar elementos que estão muito distantes: se cada par de elementos vizinhos estiver em ordem, o array inteiro estará. Isso transforma a verificação em uma única passagem pelos n-1 pares, que pode parar na primeira inversão.
Ordene uma cópia e compare
Intuição
Um array ordenado é aquele que não seria alterado pela ordenação. Portanto, faça uma cópia de nums, ordene a cópia e verifique se ela corresponde à original posição por posição. Se todas as posições corresponderem, nums já estava em ordem.
Para [2, 5, 4, 9], a cópia ordenada é [2, 4, 5, 9]. A posição 1 contém 5 no original e 4 na cópia, então a resposta é false. Para [1, 3, 3, 7], a cópia é idêntica e a resposta é true.
Isso está correto, mas faz mais do que a questão pede. A ordenação custa O(n log n), cerca de 6 × 10^4 comparações para 5000 números, e a cópia ocupa O(n) de memória. Além disso, sempre lê o array inteiro, mesmo quando o primeiro par já está fora de ordem.
Algoritmo
- Copie
numspara que o original permaneça inalterado. - Ordene a cópia em ordem numérica crescente.
- Compare a cópia com
numsposição por posição. - Retorne
truese todas as posições corresponderem; caso contrário,false.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == numsCompare cada par de vizinhos
Intuição
Você não precisa da versão ordenada para saber se o array está ordenado. Um array está em ordem não decrescente exatamente quando cada elemento é menor ou igual ao que vem logo depois dele. Como ≤ é transitivo (a ≤ b e b ≤ c implicam a ≤ c), verificar os n-1 pares vizinhos abrange todos os pares de posições.
Percorra i de 1 a n-1 e compare nums[i-1] com nums[i]. Para [2, 5, 4, 9], o par (2, 5) está correto e o par (5, 4) decresce, então você retorna false ali mesmo, sem olhar para o 9. Vizinhos iguais passam, porque apenas > falha.
Cada par é comparado uma vez, então o tempo é O(n), e o índice do loop é a única memória extra, O(1). Compare os dois valores diretamente em vez de subtraí-los: com valores de até 10^9, uma diferença pode causar overflow em um int de 32 bits.
Algoritmo
- Percorra
ide 1 atén-1. - Se
nums[i-1] > nums[i], retornefalse. - Se o loop terminar, retorne
true. Um único elemento ignora o loop e está ordenado.
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
Armadilhas e casos extremos
O loop é curto, então os bugs estão nas extremidades e na comparação.
- Tratar vizinhos iguais como uma falha. Testar
nums[i-1] >= nums[i]rejeita[1, 3, 3, 7]. Apenas uma queda estrita (>) quebra a ordem. - Ler além do fim. Um loop de
0atén-1que comparanums[i]comnums[i+1]precisa parar uma iteração antes, ou lê fora do array. Começar emi = 1e comparar comi-1evita o problema. - Subtrair em vez de comparar.
nums[i] - nums[i-1] >= 0parece a mesma coisa, mas10^9 - (-10^9) = 2 × 10^9não cabe em um int de 32 bits e transborda para um número negativo, então[-1000000000, 1000000000]é considerado não ordenado. O mesmo overflow quebra um comparador de qsort escrito comox - y. - Ordenar números como texto. Em JavaScript,
sort()sem uma função de comparação coloca10antes de9, então uma verificação que ordena e compara dá respostas erradas.
Perguntas frequentes3
Como verificar se um array está ordenado?
Compare cada elemento com o próximo. Se algum elemento for maior que seu vizinho à direita, o array não está ordenado e você pode parar; se chegar ao final sem encontrar nenhum, está. Isso leva O(n) de tempo e O(1) de espaço extra.
Por que verificar os vizinhos é suficiente?
A relação de ordem é transitiva: se a ≤ b e b ≤ c, então a ≤ c. Portanto, quando cada par adjacente está em ordem, todos os pares de posições também estão em ordem. Por outro lado, qualquer array não ordenado tem pelo menos um par adjacente em que o valor diminui.
Um array com elementos iguais está ordenado?
Em ordem não decrescente, sim: [4, 4, 4] está ordenado porque nenhum elemento é maior que o próximo. Se um problema pedir uma ordem estritamente crescente, altere o teste para também rejeitar elementos vizinhos iguais.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def isSorted(nums):
# Escreva o código aquiTeste #1
Teste #2
Argumento
nums = [1, 3, 3, 7]
Saída Esperada
true