Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.
Follow up: Could you do this in O(n) runtime?
Example 1:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [0] Output: 0
Example 3:
Input: nums = [2,4] Output: 6
Example 4:
Input: nums = [8,10,2] Output: 10
Example 5:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70] Output: 127
Constraints:
1 <= nums.length <= 2 * 1040 <= nums[i] <= 231 - 1
Solution: Trie
Time complexity: O(31*2*n)
Space complexity: O(31*2*n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// Author: Huahua class Trie { public: Trie(): children(2) {} vector<unique_ptr<Trie>> children; }; class Solution { public: int findMaximumXOR(vector<int>& nums) { Trie root; // Insert a number into the trie. auto insert = [&](Trie* node, int num) { for (int i = 31; i >= 0; --i) { int bit = (num >> i) & 1; if (!node->children[bit]) node->children[bit] = std::make_unique<Trie>(); node = node->children[bit].get(); } }; // Find max xor sum of num and another element in the array. auto query = [&](Trie* node, int num) { int sum = 0; for (int i = 31; i >= 0; --i) { int bit = (num >> i) & 1; if (node->children[1 - bit]) { sum += (1 << i); node = node->children[1 - bit].get(); } else { node = node->children[bit].get(); } } return sum; }; // Insert all numbers. for (int x : nums) insert(&root, x); int ans = 0; // For each number find the maximum xor sum. for (int x : nums) ans = max(ans, query(&root, x)); return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
[…] Similar idea to https://zxi.mytechroad.com/blog/trie/leetcode-421-maximum-xor-of-two-numbers-in-an-array/ […]