LC.P2859[计算K置位下标对应元素的和]

方法一：模拟(调包)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (bicCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }

    private int bicCount(int x) {
        int cnt = 0;
        while (x > 0) {
            x &= x - 1;
            ++cnt;
        }
        return cnt;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(1)$

方法二：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (bicCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }

    private int bicCount(int x) {
        int cnt = 0;
        while (x > 0) {
            x &= x - 1; // 把最低位的 1 置为 0
            ++cnt;
        }
        return cnt;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(1)$