Easy

题目描述

给你一个整数数组 nums 和一个整数 k。让我们通过扩展标准的按位 OR 来介绍 K-or 操作。在 K-or 中，结果中的某个位置被设为 1，当且仅当 nums 中至少有 k 个数字在该位置上为 1。

返回 nums 的 K-or 值。

示例 1：

输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：
用二进制表示数字：
数字    位3   位2   位1   位0
7       0     1     1     1
12      1     1     0     0
9       1     0     0     1
8       1     0     0     0
9       1     0     0     1
15      1     1     1     1
结果=9   1     0     0     1

位0在7,9,9,15中被设置。位3在12,9,8,9,15中被设置。
只有位0和位3符合条件。结果是(1001)₂ = 9。

示例 2：

输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：没有位在所有六个数组数字中都为1，这是k=6的K-or所要求的。因此，结果是0。

示例 3：

输入：nums = [10,8,5,9,11,6,8], k = 1
输出：15
解释：由于k==1，数组的1-or等于所有元素的按位OR。因此，答案是10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15。

约束：

  • 1 <= nums.length <= 50
  • 0 <= nums[i] < 2³¹
  • 1 <= k <= nums.length

提示：

  • 从范围 [0, 31] 中固定一个 bit，然后计算 nums 中有多少个元素在该位上设置了位。
  • 当且仅当 2^bit AND x == 2^bit 时，位 bit 在整数 x 中被设置，其中 AND 是按位与操作。

解题思路

这道题考查的是位操作的应用。核心思想是对每个二进制位分别统计有多少个数字在该位上为1。

解题思路：

  1. 位统计法（推荐）：由于整数范围在 [0, 2³¹)，我们需要检查每个二进制位（0到30位）。对于每一位，遍历数组统计有多少个数字在该位上为1，如果数量 ≥ k，则在结果中设置该位。

  2. 优化思路：可以通过位掩码一次性处理，但考虑到数组长度最多50，直接遍历已经足够高效。

具体步骤：

  • 初始化结果为0
  • 遍历32个二进制位（0-31）
  • 对于每一位，统计数组中有多少个数字在该位为1
  • 如果计数 ≥ k，则在结果中设置该位
  • 返回最终结果

时间复杂度是 O(32 × n)，空间复杂度是 O(1)，其中 n 是数组长度。

代码实现

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int result = 0;
        
        for (int bit = 0; bit < 32; bit++) {
            int count = 0;
            for (int num : nums) {
                if ((num >> bit) & 1) {
                    count++;
                }
            }
            if (count >= k) {
                result |= (1 << bit);
            }
        }
        
        return result;
    }
};

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        result = 0
        
        for bit in range(32):
            count = 0
            for num in nums:
                if (num >> bit) & 1:
                    count += 1
            if count >= k:
                result |= (1 << bit)
        
        return result

public class Solution {
    public int FindKOr(int[] nums, int k) {
        int result = 0;
        
        for (int bit = 0; bit < 32; bit++) {
            int count = 0;
            foreach (int num in nums) {
                if ((num >> bit) & 1) {
                    count++;
                }
            }
            if (count >= k) {
                result |= (1 << bit);
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKOr = function(nums, k) {
    let result = 0;
    
    for (let bit = 0; bit < 32; bit++) {
        let count = 0;
        for (let num of nums) {
            if ((num >> bit) & 1) {
                count++;
            }
        }
        if (count >= k) {
            result |= (1 << bit);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(32 × n)需要检查32个二进制位，每次遍历长度为n的数组
空间复杂度O(1)只使用常数额外空间

相关题目