计算 K 置位下标对应元素的和

标签: 位运算 数组

难度: Easy

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。

整数的二进制表示中的 1 就是这个整数的 置位 。

例如，21 的二进制表示为 10101 ，其中有 3 个置位。

示例 1：

输入：nums = [5,10,1,5,2], k = 1
输出：13
解释：下标的二进制表示是： 
0 = 0002
1 = 0012
2 = 0102
3 = 0112
4 = 1002 
下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。
因此，答案为 nums[1] + nums[2] + nums[4] = 13 。

示例 2：

输入：nums = [4,3,2,1], k = 2
输出：1
解释：下标的二进制表示是： 
0 = 002
1 = 012
2 = 102
3 = 112
只有下标 3 的二进制表示中存在 k = 2 个置位。
因此，答案为 nums[3] = 1 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 105
  • 0 <= k <= 10

Submission

运行时间: 12 ms

内存: 16.1 MB

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        length = len(nums)
        ans = 0
        for i in range(length):
            if bin(i).count('1') == k:
                ans += nums[i]
        return ans

Explain

此题解通过遍历数组 nums 的所有下标，对每个下标 i 转换为二进制形式，并计算二进制中1的个数。如果1的个数等于 k，就将对应的 nums[i] 加入到结果和中。最终返回这个求和结果。

时间复杂度: O(n log n)

空间复杂度: O(1)

# 定义解题类和方法

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        length = len(nums)  # 获取数组长度
        ans = 0  # 初始化结果和为0
        for i in range(length):  # 遍历每个下标i
            # 将下标i转换为二进制，计算1的个数，并检查是否等于k
            if bin(i).count('1') == k:
                ans += nums[i]  # 如果条件满足，累加对应的数组元素
        return ans  # 返回最终的和

Explore

在计算下标的二进制中置位个数时，选择使用 `bin(i).count('1')` 方法是因为它直接转换下标为二进制字符串，然后计算字符串中'1'的出现次数，这样操作直观且容易理解。然而，这种方法不是最高效的，因为二进制字符串的生成与计数都有一定的开销。一个更高效的方法是使用 Brian Kernighan 算法来计算置位个数，该算法通过不断清除最低位的1（使用 `i &= i - 1` 操作），直到变量为0，其操作次数仅为置位的个数，这样可以显著提高计算效率。

对于 k 的取值，理论上 k 应该是一个非负整数。在实际应用中，k 的最小值应该是0（即没有任何置位），而最大值应不大于下标i能表示的最大位数的1的个数，即数组最大下标的二进制表示中的位数。如果 k 大于这个值，那么不会有任何下标的二进制中1的个数等于 k，因此函数将返回0。因此，这个算法对 k 有一个隐含的逻辑限制，即 0 <= k <= log2(数组最大下标)。

如果数组长度极大，直接遍历每个下标并检查其二进制中1的个数会导致较高的时间复杂度，特别是当数组长度达到数百万或更多时。一种可能的优化方法是预处理，即事先计算并存储所有可能下标的二进制中1的个数，这样在主循环中可以直接查询，从而避免在每次迭代中重复计算。此外，如果问题允许，可以考虑使用并行计算或其他硬件加速技术来提升处理速度。

解题类中的方法可以处理大多数输入情况，但如果 k 大于数组最大下标的位数，即 k 大于 log2(数组最大下标) 的情况，根据二进制的性质，不可能有任何下标的二进制中1的个数等于 k。因此，在这种情况下，循环内的条件 `bin(i).count('1') == k` 永远不会满足，所以函数将返回0。这种情况下，函数正确处理了输入，但结果将始终为0，这是符合预期的逻辑结果。