找出数组中的 K-or 值

难度: Easy

给你一个整数数组 nums 和一个整数 k 。让我们通过扩展标准的按位或来介绍 K-or 操作。在 K-or 操作中，如果在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值是 1 。

返回 nums 的 K-or 值。

示例 1：

输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：
用二进制表示 numbers：

Number	Bit 3	Bit 2	Bit 1	Bit 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
Result = 9	1	0	0	1

位 0 在 7, 9, 9, 15 中为 1。位 3 在 12, 9, 8, 9, 15 中为 1。 只有位 0 和 3 满足。结果是 (1001)₂ = 9。

示例 2：

输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：没有位在所有 6 个数字中都为 1，如 k = 6 所需要的。所以，答案为 0。

示例 3：

输入：nums = [10,8,5,9,11,6,8], k = 1
输出：15
解释：因为 k == 1 ，数组的 1-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

Submission

运行时间: 42 ms

内存: 16.0 MB

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        res = 0
        nums.sort()
        n = len(nums)
        start = 0
        for i in range(31):
            D = 1 << i
            while start < n and nums[start] < D:
                start += 1
            cnt = 0
            for val in nums[start:]:
                if val & D:
                    cnt += 1
                    if cnt >= k:
                        res |= D
                        break
        return res

Explain

本题解的思路首先是对数组进行排序。排序后，对于每一个位（从0到30位，共31位，因为整数的范围是到2^31），算法尝试找出有多少个数字的该位是1。通过移位操作，算法逐位检查每个数字。算法维护一个指针start，该指针指向第一个大于等于当前位值D的数字。这是因为小于D的数字在该位一定是0。从start开始，算法统计该位为1的数字数量，如果数量达到k，则将此位加入到结果res中。这种方法避免了对于每一位都从头到尾扫描整个数组。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        res = 0  # 初始化结果为0
        nums.sort()  # 排序数组
        n = len(nums)  # 数组长度
        start = 0  # 初始化start指针
        for i in range(31):  # 遍历每一位，从0到30
            D = 1 << i  # 当前位的值
            while start < n and nums[start] < D:  # 移动start直到找到第一个大于等于D的数
                start += 1
            cnt = 0  # 计数当前位为1的数字个数
            for val in nums[start:]:  # 从start开始检查每个数的当前位
                if val & D:  # 如果当前位为1
                    cnt += 1
                    if cnt >= k:  # 如果满足至少k个数字的当前位为1
                        res |= D  # 将当前位加到结果中
                        break
        return res  # 返回结果

Explore

对数组进行排序主要是为了优化位运算过程中的效率。通过排序，可以快速定位到那些在特定位上可能为1的数字，从而避免了对整个数组进行全面扫描。排序后，数组的数值从小到大排列，对于二进制来说，较大的数值在高位上更可能为1。因此，一旦确定了某一位的最小阈值D（1左移位数i得到），可以使用二分查找或线性扫描的方式迅速跳过所有小于D的数，这些数在该位上肯定为0。这种方法减少了无效的检查，提高了算法的整体效率。

指针`start`的移动逻辑是基于数组已经排序的事实。对于每一位i，计算位值D（1左移位数i）。接着算法从当前`start`位置开始扫描数组，直到找到第一个大于等于D的数字。因为数组是有序的，所以小于D的数在该位上必定是0，而大于等于D的数字在该位上可能为1。这样就能够快速定位到可能需要计数的起始位置，从而跳过无关的数值，并减少不必要的比较。这个过程可以视为一种优化的线性扫描，其效率高于从头开始的全扫描。

在每一位的处理中，一旦发现有k个数字的该位都为1，意味着在该位上，已经满足题目条件要求的至少k个1。由于我们的目标是确定哪些位在结果数字中应当为1（即在这些位上至少有k个原数组中的数字对应位为1），找到这k个1后，任何额外的1都不会改变这一位在最终结果中应该为1的事实。因此，一旦这个条件被满足，可以立即将该位加入结果，并终止当前位的进一步检查，这样做可以节省时间，避免不必要的计算。