1. 題目

給定一個非空數(shù)組，數(shù)組中元素為 a0, a1, a2, … , an-1，其中 0 ≤ ai < 2³¹ 。

找到 ai 和aj 最大的異或 (XOR) 運算結(jié)果，其中0 ≤ i, j < n 。

你能在O(n)的時間解決這個問題嗎？

示例:輸入: [3, 10, 5, 25, 2, 8]輸出: 28解釋: 最大的結(jié)果是 5 ^ 25 = 28.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. Tries樹

• 題目要求O(n)時間復(fù)雜度，兩兩異或O(n²)
• 考慮將每個數(shù)字的二進制位插入Trie樹（從高位往低位插入）O(n)
• 再遍歷每個數(shù)字bit，貪心從trie樹的異或最大路徑往下走，得到一個val，取val的最大值，O(n)時間復(fù)雜度

class Node { public:int val;Node *next[2];Node(int v = 0):val(v) {next[0] = next[1] = NULL;} }; class Trie { public:Node *root;Trie(){root = new Node();}~Trie()//析構(gòu)釋放內(nèi)存{destroy(root);}void destroy(Node *root){if(root == NULL)return;destroy(root->next[0]);destroy(root->next[1]);delete root;}void insert(int n)//插入數(shù)字的二進制位{Node *cur = root;int bit;for(int i = 31; i >= 0; --i){bit = (n>>i) & 1;if(cur->next[bit] == NULL)cur->next[bit] = new Node(bit);cur = cur->next[bit];}}int MaxXOR(int n){Node *cur = root;int val = 0, bit, anotherBit;for(int i = 31; i >= 0; --i){bit = (n>>i) & 1;anotherBit = bit^1;//取反if(cur->next[anotherBit]){val += (1<<i);cur = cur->next[anotherBit];}elsecur = cur->next[bit];}return val;} }; class Solution { public:int findMaximumXOR(vector<int>& nums) {Trie tree;int ans = INT_MIN;for(int n:nums)tree.insert(n);for(int n:nums)ans = max(ans,tree.MaxXOR(n)); return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 421. 数组中两个数的最大异或值（Trie树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。