Kira Bilangan Pasangan Adil

2563. Kira Bilangan Pasangan Adil

Kesukaran: Sederhana

Topik: Tatasusunan, Dua Penunjuk, Carian Binari, Isih

Diberikan 0-diindeks nombor tatasusunan integer bersaiz n dan dua integer bawah dan atas, kembalikan bilangan pasangan saksama.

Sepasang (i, j) adalah adil jika:

• 0 <= i < j < n, dan
• bawah <= nums[i] nums[j] <= atas

Contoh 1:

• Input: nombor = [0,1,7,4,4,5], bawah = 3, atas = 6
• Output: 6
• Penjelasan: Terdapat 6 pasangan adil: (0,3), (0,4), (0,5), (1,3), (1,4), dan (1,5) .

Contoh 2:

• Input: nombor = [1,7,9,2,5], bawah = 11, atas = 11
• Output: 1
• Penjelasan: Terdapat satu pasangan adil: (2,3).

Kekangan:

• 1 <= nums.length <= 10⁵
• bilangan panjang == n
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= bawah <= atas <= 10⁹

Petunjuk:

1. Isih tatasusunan dalam tertib menaik.
2. Untuk setiap nombor dalam tatasusunan, jejaki nombor terkecil dan terbesar dalam tatasusunan yang boleh membentuk pasangan saksama dengan nombor ini.
3. Apabila anda beralih ke nombor yang lebih besar, kedua-dua sempadan bergerak ke bawah.

Penyelesaian:

Kita boleh menggunakan pendekatan berikut:

1. Isih Tatasusunan: Isih membantu kami memanfaatkan teknik dua mata dan melakukan carian binari dengan lebih berkesan.
2. Teknik Dua Penunjuk: Untuk setiap elemen dalam tatasusunan yang diisih, kita boleh mengira julat elemen yang boleh membentuk pasangan saksama dengannya. Kami menggunakan carian binari untuk mencari julat ini.
3. Carian Perduaan untuk Had: Untuk setiap elemen nums[i], cari julat [bawah, atas] - nums[i] untuk j > i. Kami menggunakan carian binari untuk mencari indeks terkecil dan terbesar yang memenuhi julat ini.

Mari laksanakan penyelesaian ini dalam PHP: 2563. Kira Bilangan Pasangan Adil


<?php
/**
* @param Integer[] $nums
* @param Integer $lower
* @param Integer $upper
* @return Integer
*/
function countFairPairs($nums, $lower, $upper) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
* Helper function for binary search to find left boundary
*
* @param $arr
* @param $target
* @param $start
* @return int|mixed
*/
function lowerBound($arr, $target, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
* Helper function for binary search to find right boundary
*
* @param $arr
* @param $target
* @param $start
* @return int|mixed
*/
function upperBound($arr, $target, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [0, 1, 7, 4, 4, 5];
$lower = 3;
$upper = 6;
echo countFairPairs($nums, $lower, $upper);  // Output: 6
?>

Penjelasan:

1. Isih: Kami mengisih nombor tatasusunan untuk memudahkan mencari pasangan yang sah dengan carian binari.
2. Sempadan Carian Binari:
   • Untuk setiap elemen nums[i], kita dapati nilai rendah dan tinggi, yang merupakan had yang kita mahu jumlahnya termasuk.
   • Kami menggunakan dua carian binari untuk mencari julat indeks [kiri, kanan) di mana nums[i] nums[j] berada dalam [bawah, atas].
3. Mengira Pasangan: Kami menambah kiraan indeks yang sah antara kiri dan kanan untuk setiap i.

Pendekatan ini mempunyai kerumitan masa O(n log n) disebabkan oleh pengisihan dan carian binari untuk setiap elemen, yang cukup cekap untuk input yang besar.

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 Kira Bilangan Pasangan Adil. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!