Zählen Sie die Anzahl der fairen Paare

2563. Zählen Sie die Anzahl der fairen Paare

Schwierigkeit:Mittel

Themen:Array, Zwei Zeiger, Binäre Suche, Sortieren

Angesichts eines 0-indizierten ganzzahligen Arrays der Größe n und zwei Ganzzahlen unten und oben, wird die Anzahl der fairen Paare zurückgegeben.

Ein Paar (i, j) ist fair, wenn:

• 0 <= i < j < n, und
• untere <= nums[i] nums[j] <= obere

Beispiel 1:

• Eingabe: nums = [0,1,7,4,4,5], untere = 3, obere = 6
• Ausgabe: 6
• Erklärung: Es gibt 6 faire Paare: (0,3), (0,4), (0,5), (1,3), (1,4) und (1,5) .

Beispiel 2:

• Eingabe: nums = [1,7,9,2,5], untere = 11, obere = 11
• Ausgabe: 1
• Erklärung: Es gibt ein einziges faires Paar: (2,3).

Einschränkungen:

• 1 <= nums.length <= 10⁵
• nums.length == n
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= unten <= oben <= 10⁹

Hinweis:

1. Sortieren Sie das Array in aufsteigender Reihenfolge.
2. Behalten Sie für jede Zahl im Array die kleinsten und größten Zahlen im Array im Auge, die mit dieser Zahl ein faires Paar bilden können.
3. Wenn Sie zu einer größeren Zahl wechseln, verschieben sich beide Grenzen nach unten.

Lösung:

Wir können den folgenden Ansatz verwenden:

1. Sortieren Sie das Array: Das Sortieren hilft uns, die Zwei-Zeiger-Technik zu nutzen und binäre Suchen effektiver durchzuführen.
2. Zwei-Zeiger-Technik: Für jedes Element im sortierten Array können wir den Bereich der Elemente berechnen, die damit ein faires Paar bilden können. Wir verwenden die binäre Suche, um diesen Bereich zu finden.
3. Binäre Suche nach Grenzen: Suchen Sie für jedes Element nums[i] den Bereich [unten, oben] - nums[i] für j > ich. Wir verwenden die binäre Suche, um die kleinsten und größten Indizes zu finden, die diesen Bereich erfüllen.

Lassen Sie uns diese Lösung in PHP implementieren: 2563. Zählen Sie die Anzahl der fairen Paare


<?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
?>

Erläuterung:

1. Sortierung: Wir sortieren die Array-Nummern, um das Auffinden gültiger Paare mit der binären Suche zu erleichtern.
2. Binäre Suchgrenzen:
   • Für jedes Element nums[i] finden wir die unteren und oberen Werte, die die Grenzen darstellen, innerhalb derer die Summe liegen soll.
   • Wir verwenden zwei binäre Suchvorgänge, um den Indexbereich [links, rechts) zu finden, in dem nums[i] nums[j] in [unten, oben] fällt.
3. Paare zählen: Wir addieren die Anzahl der gültigen Indizes zwischen links und rechts für jedes i.

Dieser Ansatz hat eine zeitliche Komplexität von O(n log n) aufgrund der Sortierung und binären Suche für jedes Element, was für große Eingaben effizient genug ist.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der fairen Paare. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!