【 每日一题】计算 K 置位下标对应元素的和
Tag
【统计1的数量】【数组】【2024-01-25】
题目来源
解题思路
方法一:统计1的数量
思路
枚举所有的下标,将含有 k
个 1 的下标对应数组中整数加和。
思路清晰,统计 int 型整数中1的数量有多种方法:
- 迭代计算:为了计算
i
的置位个数,我们可以使用十进制转二进制的方法,每次通过i mod 2
得到最低的二进制位,在通过 ⌊ i / 2 ⌋ \lfloor i / 2 \rfloor ⌊i/2⌋ 去掉最低的二进制位,不断进行该操作直到i=0
为止; - 库函数计算:使用
_
_
b
u
i
l
t
i
n
_
p
o
p
c
o
u
n
t
(
)
\_\_builtin\_popcount()
__builtin_popcount() 统计 int 型整数对应的二进制数含有多有个
1
。
算法
class Solution {
public:
int sumIndicesWithKSetBits(vector<int>& nums, int k) {
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
if (__builtin_popcount(i) == k) {
res += nums[i];
}
}
return res;
}
};
复杂度分析
时间复杂度:
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn),
n
n
n 是数组 nums
的长度。对于每一个下标,我们需要
O
(
l
o
g
n
)
O(logn)
O(logn) 的时间计算它的置位个数。
空间复杂度: O ( 1 ) O(1) O(1)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。
原文地址:https://blog.csdn.net/weixin_54383080/article/details/135846867
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!