LC.P2917[找出数组中的K-or值]

方法一：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            int cnt1 = 0; // 统计第i位是1的个数
            for (int x : nums) {
                cnt1 += (x >> i) & 1;
            }
            if (cnt1 >= k) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogM)$，其中 $n$ 为 $nums$ 的长度，$M = max(nums)$
  • 空间复杂度：$O(1)$