XOR สูงสุดของสองตัวเลขในอาร์เรย์ใน C++

สมมติว่าเรามีอาร์เรย์ตัวเลขที่ไม่ว่าง a0, a1, a2, … , an-1 โดยที่ 0 ≤ ai <231 เราต้องหาผลลัพธ์สูงสุดของ ai XOR aj โดยที่ 0 ≤ i, j

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนด insertNode() สิ่งนี้จะใช้ val และ head

• curr :=หัว

• สำหรับผมอยู่ในช่วง 31 ถึง 0

  • bit :=val / (2^i) AND 1

  • ถ้า child[bit] ของ curr เป็นโมฆะ ดังนั้น child[bit] ของ curr :=new node

  • curr :=child[บิต] ของสกุลเงิน

• กำหนด find() วิธีการ นี่จะใช้ val และ head เป็นอินพุต

• curr :=head, ans :=0

• สำหรับผมอยู่ในช่วง 31 ถึง 0

  • bit :=val / (2^i) AND 1

  • ถ้า child[bit] ของ curr เป็นโมฆะ ดังนั้น ans :=ans OR (2^1)/p>

  • curr :=child[บิต] ของสกุลเงิน

• กลับมาอีกครั้ง

• จากวิธีหลัก ให้ทำดังนี้ −

• ตอบ :=0

• n :=ขนาดของ nums

• head :=โหนดใหม่

• สำหรับฉันในช่วง 0 ถึง n – 1, insertNode(nums[i], head)

• สำหรับฉันในช่วง 0 ถึง n – 1, ans :=สูงสุดของ ans และค้นหา (nums[i], head)

• กลับมาอีกครั้ง

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
struct Node{
   Node* child[2];
   Node(){
      child[1] = child[0] = NULL;
   }
};
class Solution {
   public:
   void insertNode(int val, Node* head){
      Node* curr = head;
      for(int i = 31; i>= 0; i--){
         int bit = (val >> i) & 1;
         if(!curr->child[bit]){
            curr->child[bit] = new Node();
         }
         curr = curr->child[bit];
      }
   }
   int find(int val, Node* head){
      Node* curr = head;
      int ans = 0;
      for(int i = 31; i>= 0; i--){
         int bit = (val >> i) & 1;
         if(curr->child[!bit]){
            ans |= (1 << i);
            curr = curr->child[!bit];
         } else {
            curr = curr->child[bit];
         }
      }
      return ans;
   }
   int findMaximumXOR(vector<int>& nums) {
      int ans = 0;
      int n = nums.size();
      Node* head = new Node();
      for(int i = 0; i < n; i++){
         insertNode(nums[i], head);
      }
      for(int i = 0; i < n; i++){
         ans = max(ans, find(nums[i], head));
      }
      return ans;
   }
};
main(){
   vector<int> v = {3,10,5,25,2,8};
   Solution ob;
   cout << (ob.findMaximumXOR(v));
}

อินพุต

[3,10,5,25,2,8]

ผลลัพธ์

28