文章

[LeetCode] 每日一题 2275. 按位与结果大于零的最长组合

题目链接

https://leetcode.cn/problems/largest-combination-with-bitwise-and-greater-than-zero

题目描述

对数组 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. 核心思路:

    • 对于一个整数,它可以表示为二进制的形式。如果我们找到数组中某一位始终为 1 的数字组合,那么该组合的按位与结果一定大于 0

    • 对于每一位,统计数组中该位为 1 的数字个数。最大值即为结果,因为这些数字可以形成按位与结果大于 0 的最长组合

  2. 实现步骤:

    • 使用一个 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;
    }
}

复杂度分析

  1. 时间复杂度:

    • 遍历数组中的每个数字:时间复杂度为 O(n)

    • 对每个数字最多处理 24 位:每个数字需要 O(1) 的时间

    • 总时间复杂度:O(n)

  2. 空间复杂度:

    • 使用了一个长度为 24 的数组存储统计结果:空间复杂度为 O(1)(与输入规模无关)

总结

本题的关键在于识别按位与的特性,利用二进制位的统计代替组合计算,从而大大降低了计算复杂度。通过简单的位运算和数组操作,解决了看似复杂的组合问题

优势:

  • 高效:时间复杂度仅为 O(n),适合处理大规模数据

  • 简单:逻辑清晰,无需复杂的组合生成

反思:

  • 如果题目对数字范围有更高要求,例如超出 24 位,算法需要适当扩展位宽以满足统计需求

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0