資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++陣列中兩數的最大異或值
假設我們有一個非空數字陣列 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231。我們需要找到 ai XOR aj 的最大結果，其中 0 ≤ i, j < n。例如，如果輸入為 [3, 10, 5, 15, 2, 8]，則輸出為 28。最大結果為 5 XOR 25 = 28。
為了解決這個問題，我們將遵循以下步驟：
定義 insertNode() 函式，它將接收 val 和 head 作為引數。
curr := head
for i in range(31, -1, -1):
bit := (val >> i) & 1
if curr 的子節點[bit] 為空，則 curr 的子節點[bit] := 新節點
curr := curr 的子節點[bit]
定義 find() 方法。它將接收 val 和 head 作為輸入。
curr := head, ans := 0
for i in range(31, -1, -1):
bit := (val >> i) & 1
if curr 的子節點[bit] 為空，則 ans := ans | (1 << i)
curr := curr 的子節點[bit]
return ans
在主方法中，執行以下操作：
ans := 0
n := nums 的大小
head := 新節點
for i in range(0, n): insertNode(nums[i], head)
for i in range(0, n): ans := max(ans, find(nums[i], head))
return ans
示例 (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
更新於：2020年5月2日
162 次瀏覽
廣告