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

难度: 简单

来源: 周赛363场次

---

给你一个下标从 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] <= 10^5
• 0 <= k <= 10
   

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
    }
}

分析与题解

---

• 位运算

  这个题目其实很简单, 我们对数组下标进行 按位与 的位运算即可.

  我们知道一个二级制数有以下的 按位与 规则, 那就是当两个二进制数的某一位都为 1时, 才会返回这一位的 1

  0b0010 & (1 << 1) = 0b0010
  
  0b0010 & (1 << 2) = 0b0000
  

  我们只需要知道 当前index下标的二进制数中大于0的位数与 k 相同即可满足题意.

  所以, 我们需要对下标index的每一位都进行按位与 操作, 并且由于 1 <= nums.length <= 1000 的条件限制, 我们只需要遍历到 2^10 已经达到了边界条件.

  所以代码如下所示.

  for(int i = 0; i <= 10; i++) {
      if ((index & (1 << i)) > 0) {
          count++;
      }
      if (count > k) {
          break;
      }
  }
  

  然后, 外部判断是否满足题意, 满足的话直接加到结果中即可.

  if (count == k) {
      result += nums.get(item);
  } 
  

  最后我们看一下整体的解题方案, 代码如下所示.

  class Solution {
      public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
          // 位运算 按位与即可
          int result = 0;
          for(int item = 0; item < nums.size(); item++) {
              int count = 0;
              for(int i = 0; i <= 10; i++) {
                  if ((item & (1 << i)) > 0) {
                      count++;
                  }
                  if (count > k) {
                      break;
                  }
              }
              if (count == k) {
                  result += nums.get(item);
              } 
          }        
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n²), 因为是需要两层遍历。
  • 空间复杂度: O(1), 常量级别的空间开辟.

  结果如下所示.