剑指 Offer 15 - 二进制中 1 的个数
# 📃 题目描述
题目链接:剑指 Offer 15. 二进制中1的个数 (opens new window)
# 🔔 解题思路
# 循环检查二进制位
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i ++) {
if (((n >> i) & 1) == 1) {
count ++;
}
}
return count;
}
}
时间复杂度 O(N)
# Brian Kernighan 算法
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
// 最后一位 1 变成 0
n &= (n - 1);
count ++;
}
return count;
}
}
时间复杂度 O(LogN)
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10