Explication détaillée de trois méthodes pour trouver l'intersection de deux tableaux en PHP

Question : Étant donné deux tableaux, écrivez une fonction pour calculer leur intersection.

Exemple 1 :

Entrée : nums1 = [1,2,2,1],nums2 = [2,2]

Sortie : [2]

Exemple 2 :

Entrée : nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Sortie : [9,4]

Remarque :

Chaque élément du résultat de sortie doit être unique.

Nous pouvons ignorer l'ordre des résultats de sortie.

Solution 1 : Itérer un tableau

Analyse d'idées :

Itérer un tableau et déterminer s'il existe un autre tableau

PHP Implémentation du code :

/**
 * @param Integer[] $nums1
 * @param Integer[] $nums2
 * @return Integer[]
 */
function intersection($nums1, $nums2) {
    $res = [];
    for($i=0;$i<count($nums1);$i++){
        if(in_array($nums1[$i],$nums2)){
            $res[] = $nums1[$i];
        }
    }
    return array_unique($res);
}

Utilisation :

$nums2 = [2,4,6,7,8,99];
$nums1 = [1,2,5,9,9,66,89,90,99,99];
var_dump(intersection($nums1, $nums2));

Analyse de complexité :

Complexité temporelle : O(mn)

Solution 2 : Intégrée Fonction de tableau

Analyse des idées :

Utilisez la fonction array_intersect() pour obtenir l'intersection des tableaux, puis utilisez array_unique() pour supprimer les doublons

Implémentation du code PHP :

/**
 * @param Integer[] $nums1
 * @param Integer[] $nums2
 * @return Integer[]
 */
function intersection($nums1, $nums2) {
    return array_unique(array_intersect($nums1,$nums2));
}

Utilisation :

$nums2 = [2,4,6,7,8,99];
$nums1 = [1,2,5,9,9,66,89,90,99,99];
var_dump(intersection($nums1, $nums2));

Solution 3 : Solution brutale

Analyse des idées :

Fusionner d'abord les deux tableaux en un seul array , puis parcourez deux fois pour trouver

Implémentation du code PHP :

/**
 * @param Integer[] $nums1
 * @param Integer[] $nums2
 * @return Integer[]
 */
function intersection($nums1, $nums2) {
    $new_arr = array_merge(array_unique($nums1),array_unique($nums2));
    $res = [];
    for($i=0;$i<count($new_arr);$i++){
        for($j=$i+1;$j<count($new_arr);$j++){
            if($new_arr[$i] == $new_arr[$j]){
                $res[] = $new_arr[$i];
            }
        }
    }
    return array_unique($res);
}

Utilisation :

$nums2 = [2,4,6,7,8,99];
$nums1 = [1,2,5,9,9,66,89,90,99,99];
var_dump(intersection($nums1, $nums2));

Analyse de complexité :

Complexité temporelle : O(n ^ 2)

Solution 4 : Doubles pointeurs

Analyse des idées :

Triez d'abord les deux tableaux et avancez dans les doubles pointeurs pour rechercher

Code PHP implémentation :

/**
 * @param Integer[] $nums1
 * @param Integer[] $nums2
 * @return Integer[]
 */
function intersection($nums1, $nums2) {
    sort($nums1);
    sort($nums2);
    $i = $j = 0;
    $res = [];
    while($i < count($nums1) && $j < count($nums2)){
        if($nums1[$i] == $nums2[$j]){
            $res[] = $nums1[$i];
            $i++;
            $j++;
        }elseif($nums1[$i] < $nums2[$j]){
            $i++;
        }elseif($nums1[$i] > $nums2[$j]){
            $j++;
        }
    }
    return array_unique($res);
}

Utilisation :

$nums2 = [2,4,6,7,8,99];
$nums1 = [1,2,5,9,9,66,89,90,99,99];
var_dump(intersection($nums1, $nums2));

Analyse de complexité :

Complexité temporelle : O(nlogn)

Plus de connaissances liées à PHP, veuillez visiter tutoriel php!

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!