Hard

题目描述

给你一个下标从 0 开始的整数数组 nums。如果一对整数 x 和 y 满足以下条件，则称为 强数对：

  • |x - y| <= min(x, y)

你需要从 nums 中选出两个整数组成强数对，使得该数对的按位异或（XOR）值在数组所有强数对中达到 最大值。

返回数组 nums 所有可能的强数对中，XOR 值的最大值。

注意，你可以选择同一个整数两次来组成数对。

示例 1：

输入: nums = [1,2,3,4,5]
输出: 7
解释: 数组 nums 中有 11 个强数对: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5)。
这些数对中异或值最大的是 3 XOR 4 = 7。

示例 2：

输入: nums = [10,100]
输出: 0
解释: 数组 nums 中有 2 个强数对: (10, 10) 和 (100, 100)。
这些数对中异或值最大的是 10 XOR 10 = 0，因为 (100, 100) 也产生 100 XOR 100 = 0。

示例 3：

输入: nums = [500,520,2500,3000]
输出: 1020
解释: 数组 nums 中有 6 个强数对: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000)。
这些数对中异或值最大的是 500 XOR 520 = 1020，因为其他非零异或值只有 2500 XOR 3000 = 636。

约束条件：

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 2^20 - 1

解题思路

解题思路

这道题需要找到满足强数对条件的所有数对中，异或值最大的数对。

核心观察

  1. 强数对条件简化：对于 x ≤ y，条件 |x - y| ≤ min(x, y) 可以简化为 y - x ≤ x，即 y ≤ 2x
  2. 排序优化：先对数组排序，这样可以利用有序性快速确定强数对范围

解法一：字典树（Trie）+ 滑动窗口

这是最优解法，时间复杂度 O(n log max_val)。

核心思想：

  • 对数组排序后，对每个 x，只需考虑范围 [x, 2x] 内的数字
  • 使用字典树存储当前窗口内的数字，支持快速查询最大异或值
  • 使用滑动窗口维护有效范围，当窗口左端点不满足条件时移除

解法二：暴力枚举

直接枚举所有数对，检查是否为强数对，时间复杂度 O(n²)。适用于小规模数据。

推荐使用字典树解法，它在处理异或最值问题时非常高效，通过贪心地从高位到低位选择不同的位来最大化异或值。

代码实现

class Solution {
private:
    struct TrieNode {
        TrieNode* children[2];
        int count;
        TrieNode() : count(0) {
            children[0] = children[1] = nullptr;
        }
    };
    
    class Trie {
    private:
        TrieNode* root;
        
    public:
        Trie() {
            root = new TrieNode();
        }
        
        void insert(int num) {
            TrieNode* node = root;
            for (int i = 19; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (!node->children[bit]) {
                    node->children[bit] = new TrieNode();
                }
                node = node->children[bit];
                node->count++;
            }
        }
        
        void remove(int num) {
            TrieNode* node = root;
            for (int i = 19; i >= 0; i--) {
                int bit = (num >> i) & 1;
                node = node->children[bit];
                node->count--;
            }
        }
        
        int getMaxXor(int num) {
            TrieNode* node = root;
            int result = 0;
            for (int i = 19; i >= 0; i--) {
                int bit = (num >> i) & 1;
                int oppositeBit = 1 - bit;
                if (node->children[oppositeBit] && node->children[oppositeBit]->count > 0) {
                    result |= (1 << i);
                    node = node->children[oppositeBit];
                } else {
                    node = node->children[bit];
                }
            }
            return result;
        }
    };
    
public:
    int maximumStrongPairXor(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        Trie trie;
        int maxXor = 0;
        int left = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            trie.insert(nums[right]);
            
            while (nums[right] > 2 * nums[left]) {
                trie.remove(nums[left]);
                left++;
            }
            
            maxXor = max(maxXor, trie.getMaxXor(nums[right]));
        }
        
        return maxXor;
    }
};

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.count = 0
        
        class Trie:
            def __init__(self):
                self.root = TrieNode()
            
            def insert(self, num):
                node = self.root
                for i in range(19, -1, -1):
                    bit = (num >> i) & 1
                    if bit not in node.children:
                        node.children[bit] = TrieNode()
                    node = node.children[bit]
                    node.count += 1
            
            def remove(self, num):
                node = self.root
                for i in range(19, -1, -1):
                    bit = (num >> i) & 1
                    node = node.children[bit]
                    node.count -= 1
            
            def get_max_xor(self, num):
                node = self.root
                result = 0
                for i in range(19, -1, -1):
                    bit = (num >> i) & 1
                    opposite_bit = 1 - bit
                    if opposite_bit in node.children and node.children[opposite_bit].count > 0:
                        result |= (1 << i)
                        node = node.children[opposite_bit]
                    else:
                        node = node.children[bit]
                return result
        
        nums.sort()
        trie = Trie()
        max_xor = 0
        left = 0
        
        for right in range(len(nums)):
            trie.insert(nums[right])
            
            while nums[right] > 2 * nums[left]:
                trie.remove(nums[left])
                left += 1
            
            max_xor = max(max_xor, trie.get_max_xor(nums[right]))
        
        return max_xor

public class Solution {
    private class TrieNode {
        public TrieNode[] Children = new TrieNode[2];
        public int Count = 0;
    }
    
    private class Trie {
        private TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public void Insert(int num) {
            TrieNode node = root;
            for (int i = 19; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (node.Children[bit] == null) {
                    node.Children[bit] = new TrieNode();
                }
                node = node.Children[bit];
                node.Count++;
            }
        }
        
        public void Remove(int num) {
            TrieNode node = root;
            for (int i = 19; i >= 0; i--) {
                int bit = (num >> i) & 1;
                node = node.Children[bit];
                node.Count--;
            }
        }
        
        public int GetMaxXor(int num) {
            TrieNode node = root;
            int result = 0;
            for (int i = 19; i >= 0; i--) {
                int bit = (num >> i) & 1;
                int oppositeBit = 1 - bit;
                if (node.Children[oppositeBit] != null && node.Children[oppositeBit].Count > 0) {
                    result |= (1 << i);
                    node = node.Children[oppositeBit];
                } else {
                    node = node.Children[bit];
                }
            }
            return result;
        }
    }
    
    public int MaximumStrongPairXor(int[] nums) {
        Array.Sort(nums);
        Trie trie = new Trie();
        int maxXor = 0;
        int left = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            trie.Insert(nums[right]);
            
            while (nums[right] > 2 * nums[left]) {
                trie.Remove(nums[left]);
                left++;
            }
            
            maxXor = Math.Max(maxXor, trie.GetMaxXor(nums[right]));
        }
        
        return maxXor;
    }
}

var maximumStrongPairXor = function(nums) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.count = 0;
        }
    }
    
    class Trie {
        constructor() {
            this.root = new TrieNode();
        }
        
        insert(num) {
            let node = this.root;
            for (let i = 19; i >= 0; i--) {
                const bit = (num >> i) & 1;
                if (!node.children[bit]) {
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
                node.count++;
            }
        }
        
        remove(num) {
            let node = this.root;
            for (let i = 19; i >= 0; i--) {
                const bit = (num >> i) & 1;
                node = node.children[bit];
                node.count--;
            }
        }
        
        getMaxXor(num) {
            let node = this.root;
            let result = 0;
            for (let i = 19; i >= 0; i--) {
                const bit = (num >> i) & 1;
                const oppositeBit = 1 - bit;
                if (node.children[oppositeBit] && node.children[oppositeBit].count > 0) {
                    result |= (1 << i);
                    node = node.children[oppositeBit];
                } else {
                    node = node.children[bit];
                }
            }
            return result;
        }
    }
    
    nums.sort((a, b) => a - b);
    const trie = new Trie();
    let maxXor = 0;
    let left = 0;
    
    for (let right = 0; right < nums.length; right++) {
        trie.insert(nums[right]);
        
        while (nums[right] > 2 * nums[left]) {
            trie.remove(nums[left]);
            left++;
        }
        
        maxXor = Math.max(maxXor, trie.getMaxXor(nums[right]));
    }
    
    return maxXor;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型字典树解法暴力解法
时间复杂度O(n log V)O(n²)
空间复杂度O(n log V)O(1)

其中 n 是数组长度，V 是数组中的最大值（约为 2²⁰）。字典树解法中的 log V 来自于每个数字的二进制位数。

相关题目