. Cari Jarak Pasangan Terkecil K-th-tutorial php-php.cn

. Find K-th Smallest Pair Distance

719. Cari Jarak Pasangan Terkecil K-th

Kesukaran:Sukar

Topik:Tatasusunan, Dua Penunjuk, Carian Binari, Isih

jarak sepasanginteger a dan b ditakrifkan sebagai perbezaan mutlak antara a dan b.

Diberi nombor tatasusunan integer dan integer k, kembalikanjarak^{terkecil k}antara semua pasangannombor[i] dan nombor[j] dengan 0 <= i < j < nombor.panjang.

Contoh 1:

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

(1,3) -> 2 (1,1) -> 0 (3,1) -> 2 Maka pasangan jarak 1

st^{terkecil ialah (1,1), dan jaraknya ialah 0.}

Contoh 2:

Input:angka = [1,1,1], k = 2
Output:0

Contoh 3:

Input:angka = [1,6,1], k = 3
Output:5

Kekangan:

Petunjuk:

Penyelesaian:

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

Pendekatan:

Isih Tatasusunan: Pertama, susun nombor tatasusunan. Isih membantu dalam mengira bilangan pasangan dengan jarak yang 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 batas 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 terkecil ke-k. Nilai rendah dan tinggi mentakrifkan julat carian semasa untuk jarak. Nilai pertengahan disemak menggunakan fungsi countPairsWithDistanceLessThanOrEqualTo. Bergantung pada keputusan, 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).

Hubungi Pautan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi

repositoribintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna buat saya!

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