Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28.
A:
O(n^2) cause TLE
然后就是自己build Trie ( 只需要2个child 。深度固定)
同时,我这里走了一个弯路。 就是build 好了以后,我抛弃了之前的value, 而这样导致一个问题,就是每次分方向的时候, 即使每个parent都有2个child,也要判断4种情况。
不如直接给定一个值,而去决定往哪个方向go down the Tire.更简洁
class Solution { public: int findMaximumXOR(vector<int>& nums) { TrieNode* root = new TrieNode(); // get the max_xor while building the Trie for (auto val : nums) { auto p = root; for (int i = 31; i >= 0; i--) { int mask = 1 << i; if (val & mask) { if (not p->one) { TrieNode* tmp = new TrieNode(); p->one = tmp; } p = p->one; } else { if (not p->zero) { TrieNode* tmp = new TrieNode(); p->zero = tmp; } p = p->zero; } } } int max_xor = 0; // to avoid compare 4 possible combination of the Trie p0, p1, we get the max for each value for (auto val : nums) { auto p = root; int cur_max = 0; for (int i = 31; i >= 0; i--) { int mask = 1 << i; if (val & mask) { if (p->zero) { cur_max += mask; p = p->zero; } else { p = p->one; } } else { if (p->one) { cur_max += mask; p = p->one; } else { p = p->zero; } } } max_xor = max(max_xor, cur_max); } return max_xor; } private: struct TrieNode { TrieNode* zero; TrieNode* one; }; };
No comments:
Post a Comment