Bitweises XOR aller Paarungen

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

2425. Bitweises XOR aller Paarungen

Schwierigkeit:Mittel

Themen:Array, Bit-Manipulation

Gegeben sind zwei 0-indizierte Arrays, nums1 und nums2, die nicht negative ganze Zahlen enthalten. Ein Array nums3 enthält das bitweise XOR aller Paarungen zwischen nums1 und nums2 (jede Ganzzahl in nums1 wird mit jeder Ganzzahl in nums2 genau einmal gepaart). Gibt das bitweise XOR aller Ganzzahlen in nums3 zurück.

Beispiel 1:

• Eingabe: nums1 = [2,1,3], nums2 = [10,2,5,0]
• Ausgabe: 13
• Erklärung: Ein mögliches nums3 Array ist [8,0,7,2,11,3,4,1,9,1,6,3]. Das bitweise XOR aller dieser Zahlen ist 13.

Beispiel 2:

• Eingabe: nums1 = [1,2], nums2 = [3,4]
• Ausgabe: 0
• Erklärung:Möglich nums3 ist [2,5,1,6]. 2 ^ 5 ^ 1 ^ 6 = 0.

Einschränkungen:

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

Hinweis: Überlegen Sie, wie sich die Anzahl jeder einzelnen Ganzzahl auf die endgültige Antwort auswirkt. Wenn nums1 die Länge m hat und nums2 die Länge n hat, wird jede Zahl in nums1 n mal wiederholt und jede Zahl in nums2 wird m mal in der XOR-Summe wiederholt.

Lösung:

Die wichtigste Beobachtung ist, dass die XOR-Operation assoziativ und kommutativ ist. Außerdem x ^ x == 0. Wenn also eine Zahl in der XOR-Summe gerade oft vorkommt, hebt sie sich auf. Wir müssen nur Zahlen berücksichtigen, die ungerade oft vorkommen.

Jede Zahl in nums1 kommt nmal in der XOR-Summe vor, und jede Zahl in nums2 kommt mmal vor. Wir können die Bits jeder Zahl durchlaufen und zählen, wie oft jedes Bit insgesamt gesetzt ist. Wenn die Gesamtzahl eines Bits ungerade ist, trägt sie zum endgültigen XOR-Ergebnis bei.

Der bereitgestellte PHP-Code implementiert diesen Ansatz effizient. Die zeitliche Komplexität beträgt O(m n), da wir nums1 und nums2 einmal durchlaufen. Die Raumkomplexität beträgt O(1), da wir eine konstante Menge an zusätzlichem Raum verbrauchen.

Das obige ist der detaillierte Inhalt vonBitweises XOR aller Paarungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!