数组中每个数与其他数的最大位差计算问题求解

核心思路 #

位差本质是两个数异或结果的二进制置位数量（即汉明距离）。由于所有数仅占20位（小于100万，2^20=1048576刚好覆盖），可以用**字典树（Trie）**将时间复杂度从O(N²)优化到O(N×20)，完美适配大规模数组。

具体步骤 #

1. 构建20位字典树

   • 将每个数转换为20位二进制（高位补0，确保统一长度）。
   • 从最高位到最低位，依次将二进制位插入字典树：每个节点包含0、1两个子节点，不存在则创建。

2. 查询每个数的最大位差

   • 对数组中的每个数，同样转换为20位二进制，从最高位到最低位遍历字典树：
     • 每一步优先选择与当前位相反的子节点（这样异或后该位为1，增加置位数量）；
     • 若相反节点不存在，则选择相同节点；
     • 每成功选择相反节点，就将当前位的贡献（1）加入总计数。
   • 最终得到的计数就是该数与数组中其他数的最大位差。

示例验证 #

以输入数组[3,5,4]为例：

• 3的20位二进制：00000000000000000011
• 5的20位二进制：00000000000000000101
• 4的20位二进制：00000000000000000100

构建字典树后，查询3时：

• 高位到第3位均为0，无对应1节点，只能走0；
• 第2位为0，选择1节点（存在，对应5、4的第2位），计数+1；
• 第1位为1，选择0节点（存在，对应4的第1位），计数+1；
• 第0位为1，选择0节点（存在，对应4的第0位），计数+1；
• 总计数3，与示例输出一致。

代码实现思路（Python） #

class TrieNode:
    def __init__(self):
        self.children = [None, None]

def build_trie(nums, bits=20):
    root = TrieNode()
    for num in nums:
        node = root
        for i in range(bits-1, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]
    return root

def max_bit_diff(num, root, bits=20):
    node = root
    count = 0
    for i in range(bits-1, -1, -1):
        bit = (num >> i) & 1
        opp_bit = 1 - bit
        if node.children[opp_bit]:
            count += 1
            node = node.children[opp_bit]
        else:
            node = node.children[bit]
    return count

# 测试示例
nums = [3,5,4]
root = build_trie(nums)
output = [max_bit_diff(num, root) for num in nums]
print(output)  # 输出: [3,2,3]

注意事项 #

• 若数组中存在重复元素，查询时无需特殊处理：因为即使遍历到自身的路径，只要数组中还有其他元素，优先选择相反位的逻辑会自动跳过自身（除非所有元素都相同，此时最大位差为0）。
• 20位的设定刚好覆盖所有小于100万的正整数，无需调整位数。

内容的提问来源于stack exchange，提问作者tangerinescorpion