719. Encontre a K-ésima menor distância do par

Dificuldade: Difícil

Tópicos: Matriz, dois ponteiros, pesquisa binária, classificação

A distância de um par de inteiros aeb é definida como a diferença absoluta entre a e b.

Dado um array inteiro nums e um inteiro k, retorne a k^ésima menor distância entre todos os pares nums[i] e nums[j] onde 0 .

Exemplo 1:

• Entrada: números = [1,3,1], k = 1
• Saída: 0
• Explicação: Aqui estão todos os pares:

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

Então o 1^st menor par de distância é (1,1) e sua distância é 0.

Exemplo 2:

• Entrada: números = [1,1,1], k = 2
• Saída: 0

Exemplo 3:

• Entrada: números = [1,6,1], k = 3
• Saída: 5

Restrições:

• n == nums.comprimento
• 2 4
• 0 6
• 1

Dica:

1. Pesquisa binária pela resposta. Como você pode verificar quantos pares têm distância

Solução:

Podemos usar uma combinação de pesquisa binária e técnica de dois ponteiros. Aqui está uma abordagem passo a passo para resolver esse problema:

Abordagem:

1. Classificar o array: primeiro, classifique os números do array. A classificação ajuda a calcular com eficiência o número de pares com distância menor ou igual a um determinado valor.

2. Pesquisa binária por distância: Use a pesquisa binária para encontrar a k-ésima menor distância. O espaço de busca para as distâncias varia de 0 (a menor distância possível) a max(nums) - min(nums) (a maior distância possível).

3. Contar pares com distância ≤ meio: Para cada valor médio na pesquisa binária, conte o número de pares com distância menor ou igual a meio. Isso pode ser feito de forma eficiente usando uma abordagem de dois ponteiros.

4. Ajustar intervalo de pesquisa binária: Dependendo do número de pares com distância menor ou igual a meio, ajuste o intervalo de pesquisa binária. Se a contagem for menor que k, aumente o limite inferior; caso contrário, diminua o limite superior.

Vamos implementar esta solução em PHP: 719. Encontre a K-ésima menor distância do par

Explicação:

• countPairsWithDistanceLessThanOrEqualTo: Esta função conta quantos pares têm uma distância menor ou igual a mid. Ele usa dois ponteiros, onde right é o elemento atual e left é ajustado até que a diferença entre nums[right] e nums[left] seja menor ou igual a mid.

• smallestDistancePair: Esta função usa pesquisa binária para encontrar a k-ésima menor distância. Os valores baixo e alto definem o intervalo de pesquisa atual para as distâncias. O valor médio é verificado usando a função countPairsWithDistanceLessThanOrEqualTo. Dependendo do resultado, o espaço de pesquisa é ajustado.

Este algoritmo encontra com eficiência a k-ésima menor distância do par com uma complexidade de tempo de O(n log(max(nums) - min(nums)) n log n).

Links de contato

Se você achou esta série útil, considere dar uma estrela ao repositório no GitHub ou compartilhar a postagem em suas redes sociais favoritas ?. Seu apoio significaria muito para mim!

Se você quiser mais conteúdo útil como este, sinta-se à vontade para me seguir:

• LinkedIn
• GitHub