. Cari Jarak Pasangan Terkecil K-th

719. Cari Jarak Pasangan Terkecil K-th

Kesukaran: Sukar

Topik: Tatasusunan, Dua Penunjuk, Carian Binari, Isih

jarak sepasang integer a dan b ditakrifkan sebagai perbezaan mutlak antara a dan b.

Diberi nombor tatasusunan integer dan integer k, kembalikan k^th jarak terkecil di antara semua pasangan nums[i] dan nums[j] dengan 0 < ;= i < j < num.panjang.

Contoh 1:

• Input: nombor = [1,3,1], k = 1
• Output: 0
• Penjelasan: Ini semua pasangan:

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




Kemudian pasangan jarak terkecil 1st ialah (1,1), dan jaraknya ialah 0.

Contoh 2:



Input: nombor = [1,1,1], k = 2

Output: 0


Contoh 3:



Input: nombor = [1,6,1], k = 3

Output: 5


Kekangan:


n == angka.panjang
2 <= n <= 104

0 <= angka[i] <= 106

1 <= k <= n * (n - 1) / 2


Petunjuk:


Carian binari untuk jawapannya. Bagaimanakah anda boleh menyemak berapa banyak pasangan mempunyai jarak <= X?


Penyelesaian:

Kita boleh menggunakan gabungan carian binari dan teknik dua mata. Berikut ialah pendekatan langkah demi langkah untuk menyelesaikan masalah ini:


  
  
  Pendekatan:



Isih Tatasusunan: Mula-mula, susun nombor tatasusunan. Isih membantu dalam mengira bilangan pasangan dengan jarak kurang daripada atau sama dengan nilai yang diberikan dengan cekap.
Carian Binari pada Jarak: Gunakan carian binari untuk mencari jarak terkecil ke-k. Ruang carian untuk jarak berjulat dari 0 (jarak terkecil yang mungkin) hingga maks(bilangan) - min(bilangan) (jarak terbesar yang mungkin).
Kira Pasangan dengan Jarak ≤ Pertengahan: Untuk setiap nilai pertengahan dalam carian binari, kira bilangan pasangan dengan jarak kurang daripada atau sama dengan pertengahan. Ini boleh dilakukan dengan cekap menggunakan pendekatan dua mata.
Laraskan Julat Carian Perduaan: Bergantung pada bilangan pasangan dengan jarak kurang daripada atau sama dengan pertengahan, laraskan julat carian binari. Jika kiraan kurang daripada k, tambahkan batas bawah; jika tidak, kurangkan sempadan atas.


Mari laksanakan penyelesaian ini dalam PHP: 719. Cari Jarak Pasangan Terkecil K-th


  
  
  Penjelasan:



countPairsWithDistanceLessThanOrEqualTo: Fungsi ini mengira bilangan pasangan yang mempunyai jarak kurang daripada atau sama dengan pertengahan. Ia menggunakan dua penunjuk, di mana kanan ialah elemen semasa dan kiri dilaraskan sehingga perbezaan antara nums[kanan] dan nums[kiri] adalah kurang daripada atau sama dengan pertengahan.
smallestDistancePair: Fungsi ini menggunakan carian binari untuk mencari jarak ke-k terkecil. Nilai rendah dan tinggi mentakrifkan julat carian semasa untuk jarak. Nilai pertengahan disemak menggunakan fungsi countPairsWithDistanceLessThanOrEqualTo. Bergantung pada hasil carian, ruang carian dilaraskan.


Algoritma ini cekap mencari jarak pasangan terkecil ke-k dengan kerumitan masa O(n log(maks(bilangan) - min(bilangan)) + n log n).

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . Cari Jarak Pasangan Terkecil K-th. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!