3141：最大汉明距离（★★）

2024-05-09 约 574 字预计阅读 2 分钟次阅读

力扣第 3141 题

题目

给定一个数组 nums 和一个整数 m，每个元素 nums[i] 满足 0 <= nums[i] < 2^m，返回数组 answer。answer 数组应该与 nums 有相同的长度，每个元素 answer[i] 表示 nums[i] 和数组中其它任何元素 nums[j] 的最大 汉明距离。

两个二进制整数之间的 汉明距离 定义为对应位上二进制位不同的数量（如果需要，添加前置零）。

示例 1：

输入：nums = [9,12,9,11], m = 4

输出：[2,3,2,3]

解释：

二进制表示为 nums = [1001,1100,1001,1011]。

每个下标的最大汉明距离为：

nums[0]：1001 与 1100 距离为 2。
nums[1]：1100 与 1011 距离为 3。
nums[2]：1001 与 1100 距离为 2。
nums[3]：1011 与 1100 距离为 3。

示例 2：

输入：nums = [3,4,6,10], m = 4

输出：[3,3,2,3]

解释：

二进制表示为 nums = [0011,0100,0110,1010]。

每个下标的最大汉明距离为：

nums[0]：0011 与 0100 距离为 3。
nums[1]：0100 与 0011 距离为 3。
nums[2]：0110 与 1010 距离为 2。
nums[3]：1010 与 0100 距离为 3。

提示：

1 <= m <= 17
2 <= nums.length <= 2^m
0 <= nums[i] < 2^m

分析

等价于求 nums[i] 的反码与数组中任意元素的最短距离
可以用多源 bfs 预处理出 [0,2^m) 每个数到数组元素的最短距离

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def maxHammingDistances(self, nums: List[int], m: int) -> List[int]:
        N = 1<<m
        dq = set(nums)
        d = [inf]*N
        for x in nums:
            d[x] = 0
        while dq:
            tmp,dq = dq,[]
            for u in tmp:
                for i in range(m):
                    v = u^1<<i
                    if d[v]==inf:
                        d[v] = d[u]+1
                        dq.append(v)
        return [m-d[x^(N-1)] for x in nums]

849 ms

目录

3141：最大汉明距离（★★）

题目

分析

解答