[LeetCode] 每日一题 2275. 按位与结果大于零的最长组合
题目链接
题目描述
对数组 nums
执行 按位与 相当于对数组 nums
中的所有整数执行 按位与 。
例如,对
nums = [1, 5, 3]
来说,按位与等于1 & 5 & 3 = 1
。同样,对
nums = [7]
而言,按位与等于7
。
给你一个正整数数组 candidates
。计算 candidates
中的数字每种组合下 按位与 的结果。
返回按位与结果大于 0
的 最长 组合的长度。
示例输入
示例 1
输入:candidates = [16,17,71,62,12,24,14]
输出:4
解释:组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。
组合长度是 4 。
可以证明不存在按位与结果大于 0 且长度大于 4 的组合。
注意,符合长度最大的组合可能不止一种。
例如,组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。
示例 2
输入:candidates = [8,8]
输出:2
解释:最长组合是 [8,8] ,按位与结果 8 & 8 = 8 > 0 。
组合长度是 2 ,所以返回 2 。
提示
1 <= candidates.length <= 10^5
1 <= candidates[i] <= 10^7
题解
解题思路
核心思路:
对于一个整数,它可以表示为二进制的形式。如果我们找到数组中某一位始终为 1 的数字组合,那么该组合的按位与结果一定大于 0
对于每一位,统计数组中该位为 1 的数字个数。最大值即为结果,因为这些数字可以形成按位与结果大于 0 的最长组合
实现步骤:
使用一个
count
数组,长度为 24,因为题目中数组的范围是 [1, 10^7],而 10^7 < 2^24,因此 24 位足以表示任意数字遍历数组,对每个数字的二进制表示逐位处理,统计每个位为 1 的次数
遍历统计结果,取
count
数组的最大值作为答案
代码实现
class Solution {
public int largestCombination(int[] candidates) {
// 1 <= candidates[i] <= 10^7
int[] count = new int[24];
for (int candidate : candidates) {
for (int i = 0; candidate > 0; i++) {
// 统计当前位是否为 1
count[i] += candidate & 1;
// 右移处理下一位
candidate >>= 1;
}
}
int ans = 0;
for (int i = 0; i < 24; i++) {
ans = Math.max(ans, count[i]);
}
return ans;
}
}
复杂度分析
时间复杂度:
遍历数组中的每个数字:时间复杂度为 O(n)
对每个数字最多处理 24 位:每个数字需要 O(1) 的时间
总时间复杂度:O(n)
空间复杂度:
使用了一个长度为 24 的数组存储统计结果:空间复杂度为 O(1)(与输入规模无关)
总结
本题的关键在于识别按位与的特性,利用二进制位的统计代替组合计算,从而大大降低了计算复杂度。通过简单的位运算和数组操作,解决了看似复杂的组合问题
优势:
高效:时间复杂度仅为 O(n),适合处理大规模数据
简单:逻辑清晰,无需复杂的组合生成
反思:
如果题目对数字范围有更高要求,例如超出 24 位,算法需要适当扩展位宽以满足统计需求
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。