สมมติว่าเรามีอาร์เรย์ตัวเลขที่ไม่ว่าง 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