XOR-Abfragen eines Subarrays

1310. XOR-Abfragen eines Subarrays

Schwierigkeit:Mittel

Themen: Array, Bitmanipulation, Präfixsumme

Sie erhalten ein Array arr positiver Ganzzahlen. Sie erhalten auch die Array-Abfragen, wobei query[i] = [left_i, right_i].

Für jede Abfrage berechne ich das XOR von Elementen von links_i nach rechts_i (das heißt, arr[left_i] XOR arr[left_i 1] XOR ... XOR arr[right_i] ).

Gib eine Array-Antwort zurück, wobei Antwort[i] die Antwort auf die i^teAbfrage ist.

Beispiel 1:

• Eingabe: arr = [1,3,4,8], Abfragen = [[0,1],[1,2],[0,3],[3,3]]
• Ausgabe: [2,7,14,8]
• Erklärung: Die binäre Darstellung der Elemente im Array ist:

  1 = 0001
  3 = 0011
  4 = 0100
  8 = 1000

Die XOR-Werte für Abfragen sind:

  [0,1] = 1 xor 3 = 2
  [1,2] = 3 xor 4 = 7
  [0,3] = 1 xor 3 xor 4 xor 8 = 14
  [3,3] = 8

Beispiel 2:

• Eingabe: arr = [4,8,2,10], Abfragen = [[2,3],[1,3],[0,0],[0,3]]
• Ausgabe: [8,0,4,4]

Einschränkungen:

• 1 <= arr.length, query.length <= 3 * 10⁴
• 1 <= arr[i] <= 10⁹
• queries[i].length == 2
• 0 <= links_i <= rechts_i < arr.länge

Hinweis:

1. Was ist das Ergebnis von x ^ y ^ x ?
2. Berechnen Sie die Präfixsumme für XOR.
3. Verarbeiten Sie die Abfragen mit den Präfix-Summenwerten.

Lösung:

Wir können die Präfix-XOR-Technik verwenden. So funktioniert es:

Ansatz:

1. Präfix-XOR-Array: Wir berechnen ein Präfix-XOR-Array, wobei prefix[i] das XOR aller Elemente vom Anfang des Arrays bis zum Index i darstellt. Dadurch können wir das XOR eines beliebigen Subarrays in konstanter Zeit berechnen.

2. XOR eines Subarrays:

   • Um das XOR von Elementen zwischen den Indizes links und rechts zu berechnen:
     • Wenn links > 0 können wir das XOR von links nach rechts als prefix[right] ^ prefix[left - 1] berechnen.
     • Wenn links == 0, dann ist das Ergebnis einfach Präfix[rechts].

     Dadurch können wir jede Anfrage in konstanter Zeit beantworten, nachdem wir das Präfix-XOR-Array erstellt haben.

     Planen:

     1. Erstellen Sie das Präfix-XOR-Array.
     2. Verwenden Sie für jede Abfrage das Präfix-XOR-Array, um das XOR für den Bereich [left_i, right_i] zu berechnen.

     Lassen Sie uns diese Lösung in PHP implementieren: 1310. XOR-Abfragen eines Subarrays
     

     <?php
     /**
      * @param Integer[] $arr
      * @param Integer[][] $queries
      * @return Integer[]
      */
     function xorQueries($arr, $queries) {
         ...
         ...
         ...
         /**
          * go to ./solution.php
          */
     }
     
     // Example 1
     $arr1 = [1, 3, 4, 8];
     $queries1 = [[0, 1], [1, 2], [0, 3], [3, 3]];
     print_r(xorQueries($arr1, $queries1)); // Output: [2, 7, 14, 8]
     
     // Example 2
     $arr2 = [4, 8, 2, 10];
     $queries2 = [[2, 3], [1, 3], [0, 0], [0, 3]];
     print_r(xorQueries($arr2, $queries2)); // Output: [8, 0, 4, 4]
     ?>
     

     Nach dem Login kopieren

     Erläuterung:

     1. Präfix-XOR-Konstruktion:

        • Das Array-Präfix ist so aufgebaut, dass prefix[i] das XOR aller Elemente von arr[0] bis arr[i] enthält.
        • Wenn beispielsweise arr = [1, 3, 4, 8] ist, lautet das Präfix-Array [1, 1^3, 1^3^4, 1^3^4^8] oder [1, 2 , 6, 14].

     2. Anfragen beantworten:

        • Für jede Abfrage [links, rechts] berechnen wir das XOR des Subarrays arr[links] bis arr[rechts] mit:
          • prefix[right] ^ prefix[left - 1] (wenn left > 0)
          • Präfix[rechts] (wenn links == 0)

     Zeitkomplexität:

     • Aufbau des Präfix-Arrays: O(n), wobei n die Länge des Arrays ist.
     • Verarbeitung der Abfragen: O(q), wobei q die Anzahl der Abfragen ist.
     • Gesamtzeitkomplexität: O(n q), was für die gegebenen Einschränkungen effizient ist.

     Dieser Ansatz stellt sicher, dass wir bis zu 30.000 Abfragen auf einem Array mit einer Größe von bis zu 30.000 effizient bearbeiten können.

     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 vonXOR-Abfragen eines Subarrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!