leetcode力扣刷题系列——【找到按位或最接近 K 的子数组】

题目

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个子数组，满足子数组中所有元素按位或运算 OR 的值与 k 的绝对差尽可能小。换言之，你需要选择一个子数组 nums[l…r] 满足 |k - (nums[l] OR nums[l + 1] … OR nums[r])| 最小。
请你返回最小的绝对差值。
子数组是数组中连续的非空元素序列。

示例 1：
输入：
nums = [1,2,4,5], k = 3
输出：
0
解释：
子数组 nums[0…1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：

输入：
nums = [1,3,1,3], k = 2
输出：
1
解释：
子数组 nums[1…1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

示例 3：
输入：
nums = [1], k = 10

输出：
9
解释：
只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 109

答案

我的方法
方法有问题，这道题在力扣中属于难题，对我而言也不简单，我就是简单的先找到所有的子列表，再找到所有的or值，在进行绝对值的运算，这样子确实简单易懂，但是一旦nums足够大，我们的程序就会超出内存大小。
今天也是没有完成今天的题目，还是因为我太菜啦，想不到更牛的方法，所以今天还是分享一下官方大大的解题思路和方法吧。

class Solution(object):def minimumDifference(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""# 获取数组中所有子数组的值subnums=[]result = []for i in range(len(nums)):for j in range(i,len(nums)):subnum = nums[i:j+1]subnums.append(subnum)# 算出每一个或运算的值for sublist in subnums:if len(sublist) == 1:result.append(sublist[0])else:or_result = sublist[0]for num in sublist[1:]:or_result = or_result | numresult.append(or_result)absnums = [abs(num - k) for num in result]return min(absnums)

注：我写的方法没啥用，并没有能通过测试

官方大大的方法
思路与算法
题目给定一个数组 nums 和一个整数 k。我们需要找到 nums 的一个非空子数组，要求其所有元素的或运算结果与 k 值尽可能接近。
根据或运算的性质，当我们固定子数组的右端点，不断地向左延伸左端点时，子数组或运算结果逐渐增加，并且结果种类数不超过 log(max(nums))+1 种。因为或运算结果每次增加对应于二进制表示中某些位上由 0 变为 1，因此增加的种类数受到数值范围的限制。

因此，我们从左到右遍历 nums，并在过程中记录每个二进制上的 1 出现的最晚的位置。这些位置用于我们在延伸左端点时，遍历所有种类的或运算结果。具体的，我们用 bits_max_pos[j] 来表示第 j 个二进制为 1 出现的最晚位置，在固定右端点后，将所有的二元组 (bits_max_pos[j],j) 从大到小排序，然后依次遍历这些二元组。遍历时将或运算结果与 2^j做或运算，得到新的结果，并计算其与 k 的差值。最终答案取所有差值的最小值。
需要注意的是，对于不同的 j，其 bits_max_pos[j] 可能相同，在计算区间或运算结果时需要将它们都考虑到，因此这里需要双指针去更新或运算结果。

代码

n = len(nums)bits_max_pos = [-1] * 31res = inffor i in range(n):for j in range(31):if nums[i] >> j & 1:bits_max_pos[j] = ipos_to_bit = [(bits_max_pos[j], j) for j in range(31) if bits_max_pos[j] != -1]pos_to_bit.sort(reverse = True, key = lambda x: x[0])j, val = 0, 0while j < len(pos_to_bit):p = jwhile j < len(pos_to_bit) and pos_to_bit[j][0] == pos_to_bit[p][0]:val |= 1 << pos_to_bit[j][1]j += 1res = min(res, abs(val - k))return res