XOR au niveau du bit de tous les appariements

<code class="language-php"><?php
function xorAllPairings($nums1, $nums2) {
    $m = count($nums1);
    $n = count($nums2);
    $result = 0;

    for ($i = 0; $i < 32; $i++) {
        $count1 = 0;
        $count2 = 0;

        foreach ($nums1 as $num) {
            if (($num >> $i) & 1) {
                $count1++;
            }
        }

        foreach ($nums2 as $num) {
            if (($num >> $i) & 1) {
                $count2++;
            }
        }

        $totalCount = $count1 * $n + $count2 * $m;
        if ($totalCount % 2 != 0) {
            $result |= (1 << $i);
        }
    }

    return $result;
}

// Example 1
$nums1 = [2, 1, 3];
$nums2 = [10, 2, 5, 0];
echo xorAllPairings($nums1, $nums2); // Output: 13

// Example 2
$nums1 = [1, 2];
$nums2 = [3, 4];
echo xorAllPairings($nums1, $nums2); // Output: 0
?></code>

2425. XOR au niveau du bit de toutes les paires

Difficulté :Moyen

Sujets : Tableau, manipulation de bits

Étant donné deux tableaux indexés 0, nums1 et nums2, contenant des entiers non négatifs. Un tableau nums3 contient le XOR au niveau du bit de toutes les paires entre nums1 et nums2 (chaque entier de nums1 est associé à chaque entier de nums2 exactement une fois). Renvoie le XOR au niveau du bit de tous les entiers dans nums3.

Exemple 1 :

• Entrée : nums1 = [2,1,3], nums2 = [10,2,5,0]
• Sortie : 13
• Explication : Un tableau nums3 possible est [8,0,7,2,11,3,4,1,9,1,6,3]. Le XOR au niveau du bit de tous ces nombres est 13.

Exemple 2 :

• Entrée : nums1 = [1,2], nums2 = [3,4]
• Sortie :0
• Explication :Possible nums3 est [2,5,1,6]. 2 ^ 5 ^ 1 ^ 6 = 0.

Contraintes :

• 1 ≤ nums1.length, nums2.length ≤ 10⁵
• 0 ≤ nums1[i], nums2[i] ≤ 10⁹

Indice : Considérez comment le nombre de chaque entier individuel affecte la réponse finale. Si nums1 a une longueur m et nums2 a une longueur n, chaque nombre dans nums1 est répété n fois et chaque nombre dans nums2 est répété m fois dans la somme XOR.

Solution :

L'observation clé est que l'opération XOR est associative et commutative. Aussi, x ^ x == 0. Ainsi, si un nombre apparaît un nombre pair de fois dans la somme XOR, il s’annule. Il suffit de considérer les nombres qui apparaissent un nombre impair de fois.

Chaque nombre dans nums1 apparaît n fois dans la somme XOR, et chaque nombre dans nums2 apparaît m fois. Nous pouvons parcourir les bits de chaque nombre et compter le nombre total de fois où chaque bit est défini. Si le nombre total d'un bit est impair, cela contribue au résultat final XOR.

Le code PHP fourni implémente efficacement cette approche. La complexité temporelle est O(mn) car nous parcourons nums1 et nums2 une fois. La complexité spatiale est O(1) car nous utilisons une quantité constante d'espace supplémentaire.

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!