Find Minimum in Rotated Sorted Array

Q: Qual é a complexidade de tempo para encontrar o mínimo em um array ordenado rotacionado?

Tempo O(log n) e espaço extra O(1) com busca binária. Cada etapa mantém uma metade do intervalo, então uma lista de 5000 elementos precisa de no máximo 13 comparações. A varredura para encontrar a queda é O(n) : ela lê todos os elementos quando o mínimo está no final.

Q: Por que comparar nums[mid] com nums[hi] e não com nums[lo]?

Porque nums[hi] sempre determina de que lado está o mínimo, e nums[lo] não. Se nums[mid] > nums[hi] , os valores devem estar entre mid e hi ; caso contrário, nums[mid..hi] é crescente, e o mínimo está em mid ou antes dele. Com nums[lo] , o resultado nums[mid] > nums[lo] é compatível tanto com uma lista não rotacionada, em que o mínimo é nums[lo] , quanto com uma lista rotacionada, em que ele está à direita de mid .

Q: Como descobrir quantas vezes um array ordenado foi rotacionado?

Execute a mesma busca binária e retorne lo , o índice do mínimo, em vez de nums[lo] . Se você contar uma rotação como mover o último elemento para o início, esse índice é a quantidade de rotações. Se você contar como mover o primeiro elemento para o final, como este problema faz, a quantidade é (n - lo) mod n : em [11, 13, 15, 17, 2, 5, 9] , o mínimo está no índice 4, e 7 menos 4 resulta nos 3 valores movidos.

Q: A busca binária funciona quando o array tem valores duplicados?

Não permanece inalterado. Em [2, 2, 2, 0, 2] , nums[mid] pode ser igual a nums[hi] , e então nenhum dos lados pode ser descartado. Diminuir hi com hi = hi - 1 nesse caso é seguro, porque uma cópia de nums[hi] permanece no intervalo em mid , mas uma lista de valores iguais com um valor menor escondido entre eles passa a custar O(n) .

MédioBusca binária

+10

Uma lista de inteiros distintos foi ordenada em ordem crescente e depois rotacionada: uma quantidade de elementos, possivelmente zero, foi retirada do início e movida para o final na mesma ordem. Por exemplo, [2, 5, 9, 11, 13, 15, 17] rotacionada em 3 posições se torna [11, 13, 15, 17, 2, 5, 9]. Você recebe a lista rotacionada nums. Retorne seu menor valor em O(log n) tempo.

Função

findMin(nums: integer-array) → integer

numsinteger-array: a lista ordenada e rotacionada de números inteiros distintos
Retornainteger: o menor valor em nums

Restrições

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Todos os valores em nums são distintos.
nums é uma lista crescente rotacionada por algum k com 0 ≤ k < nums.length; k = 0 a deixa sem rotação.

Exemplos

Entrada: nums = [11, 13, 15, 17, 2, 5, 9]
Saída: 2
Explicação: Os valores sobem de 11 para 17 e depois caem para 2, onde a segunda execução começa. A busca encontra 17 > 9 no índice 3, então o mínimo está à sua direita; em seguida, 5 ≤ 9 e 2 ≤ 5 puxam hi de volta até que o intervalo seja apenas o índice 4, que contém 2.

Entrada: nums = [4, 7, 10, 12]
Saída: 4
Explicação: Esta lista foi rotacionada em 0, então ainda está ordenada e o mínimo é seu primeiro valor. Todo valor do meio é menor ou igual ao último, então hi continua se movendo para a esquerda até chegar ao índice 0, que contém 4.

Entrada: nums = [30, -6, 0, 8, 19]
Saída: -6
Explicação: Quatro valores foram movidos do início para o final, então o maior valor, 30, agora vem primeiro, e o mínimo, -6, fica no índice 1. A busca reduz o intervalo aos índices 0 e 1, vê que 30 > -6 e move lo para 1.

+17 testes ocultos ao enviar

Para ir além

Você consegue retornar o k-ésimo menor valor de nums em O(log n) tempo, sem ordená-lo?

Dicas

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

0 de 3 abertas

Solução

Uma lista ordenada rotacionada consiste em duas sequências crescentes, [11, 13, 15, 17] e depois [2, 5, 9]. O mínimo é o primeiro valor da segunda sequência, logo após o único ponto em que os valores diminuem. Percorrer a lista encontra essa queda em O(n). Comparar um valor do meio com o último valor do intervalo indica de que lado da queda está o valor do meio, então a busca binária o encontra em O(log n).

Caminhe até que os valores diminuam

Intuição

Em uma lista ordenada, cada valor é maior que o anterior. Rotacionar a lista mantém os dois trechos ordenados e cria exatamente um ponto em que isso deixa de acontecer: o maior valor seguido pelo menor. Portanto, percorra a lista da esquerda para a direita e retorne o primeiro valor que seja menor que seu vizinho à esquerda. Se não houver tal valor, a lista foi rotacionada em 0 posições e o mínimo é nums[0].

Em [11, 13, 15, 17, 2, 5, 9], o percurso passa por 13, 15 e 17, cada um maior que o valor anterior, e para no índice 4, onde 2 é menor que 17. Isso já é melhor do que encontrar o mínimo entre todos os valores, pois para na queda, mas ela pode estar em qualquer lugar. Quando a rotação moveu um elemento, como em [2, 3, 4, 5, 6, 7, 8, 1], o percurso lê a lista inteira: 5000 comparações para 5000 elementos, enquanto a busca binária precisa de 13.

Algoritmo

Para cada índice i de 1 a n-1, compare nums[i] com nums[i-1].
Se nums[i] < nums[i-1], retorne nums[i]: a segunda sequência começa ali.
Se o loop terminar, a lista não foi rotacionada: retorne nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Busca binária em relação ao último valor

Intuição

Mantenha uma promessa: o mínimo está entre lo e hi, inclusive. No início, esse intervalo corresponde à lista inteira. Observe o valor do meio e compare-o com nums[hi], o último valor do intervalo.

Se nums[mid] > nums[hi], os valores diminuem em algum ponto entre mid e hi, e o mínimo é o valor logo após essa queda, portanto está à direita de mid: defina lo = mid + 1. Caso contrário, nums[mid] < nums[hi] (os valores são distintos), então nums[mid..hi] cresce sem nenhuma queda. O mínimo é, portanto, nums[mid] ou algum valor anterior a ele, então defina hi = mid. Não avance além de mid: ele pode ser o mínimo. Cada movimento mantém a promessa e reduz o intervalo, e, quando lo se iguala a hi, o único valor restante é o mínimo.

Acompanhe o primeiro exemplo, [11, 13, 15, 17, 2, 5, 9]. O intervalo de 0 a 6 tem meio em 3, com valor 17, maior que nums[6] = 9, então lo passa a ser 4. O intervalo de 4 a 6 tem meio em 5, com valor 5, que não é maior que 9, então hi passa a ser 5. O intervalo de 4 a 5 tem meio em 4, com valor 2, que não é maior que 5, então hi passa a ser 4. Retorne nums[4] = 2.

A cada etapa, o intervalo é reduzido pela metade, então o loop executa no máximo cerca de log2(n) vezes: 13 etapas para 5000 elementos, usando dois índices de memória extra.

Algoritmo

Defina lo = 0 e hi = n-1.
Enquanto lo < hi, calcule mid = lo + (hi - lo) / 2.
Se nums[mid] > nums[hi], defina lo = mid + 1.
Caso contrário, defina hi = mid.
Quando o loop terminar, retorne nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Armadilhas e casos extremos

O laço tem quatro linhas, e cada linha tem uma versão errada tentadora.

Escrever hi = mid - 1 no segundo ramo. Esse ramo é executado quando mid pode ser o próprio mínimo. Em [3, 1, 2], o valor do meio, 1, não é maior que 2, então hi diminui para 0 e a função retorna 3.
Fazer o laço enquanto lo ≤ hi. Quando lo fica igual a hi, mid fica igual a ambos, nums[mid] > nums[hi] é falso, e hi = mid não muda nada: o laço nunca termina. Pare quando o intervalo tiver um elemento, usando lo < hi.
Comparar com nums[lo] em vez de nums[hi]. Na lista não rotacionada [1, 2, 3, 4, 5], o valor do meio, 3, é maior que nums[0] = 1, o que faz parecer que a queda está à direita; assim, a busca se afasta do mínimo verdadeiro no índice 0 e retorna 4.
Retornar lo em vez de nums[lo]. A tarefa pede o valor; o índice é a resposta para uma pergunta diferente (veja a FAQ sobre a contagem de rotações).
Presumir que a lista foi rotacionada. Uma rotação de 0 é permitida, e um código que procura uma queda sem uma alternativa acaba lendo além do fim ou não retorna nada. Retorne nums[0] quando não houver queda.

Perguntas frequentes4

Qual é a complexidade de tempo para encontrar o mínimo em um array ordenado rotacionado?

Tempo O(log n) e espaço extra O(1) com busca binária. Cada etapa mantém uma metade do intervalo, então uma lista de 5000 elementos precisa de no máximo 13 comparações. A varredura para encontrar a queda é O(n): ela lê todos os elementos quando o mínimo está no final.

Por que comparar nums[mid] com nums[hi] e não com nums[lo]?

Porque nums[hi] sempre determina de que lado está o mínimo, e nums[lo] não. Se nums[mid] > nums[hi], os valores devem estar entre mid e hi; caso contrário, nums[mid..hi] é crescente, e o mínimo está em mid ou antes dele. Com nums[lo], o resultado nums[mid] > nums[lo] é compatível tanto com uma lista não rotacionada, em que o mínimo é nums[lo], quanto com uma lista rotacionada, em que ele está à direita de mid.

Como descobrir quantas vezes um array ordenado foi rotacionado?

Execute a mesma busca binária e retorne lo, o índice do mínimo, em vez de nums[lo]. Se você contar uma rotação como mover o último elemento para o início, esse índice é a quantidade de rotações. Se você contar como mover o primeiro elemento para o final, como este problema faz, a quantidade é (n - lo) mod n: em [11, 13, 15, 17, 2, 5, 9], o mínimo está no índice 4, e 7 menos 4 resulta nos 3 valores movidos.

A busca binária funciona quando o array tem valores duplicados?

Não permanece inalterado. Em [2, 2, 2, 0, 2], nums[mid] pode ser igual a nums[hi], e então nenhum dos lados pode ser descartado. Diminuir hi com hi = hi - 1 nesse caso é seguro, porque uma cópia de nums[hi] permanece no intervalo em mid, mas uma lista de valores iguais com um valor menor escondido entre eles passa a custar O(n).

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [11, 13, 15, 17, 2, 5, 9]

Esperado