Hard

题目描述

给你一个数组 nums 和一个整数 k。你需要找到 nums 的一个子数组，使得 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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

提示：

  • 设 dp[i] 为所有以索引 i 结尾的子数组的按位 OR 值的集合。
  • 从 nums[i] 开始，通过从 i 向左逐个包含元素来计算按位 OR 结果。注意只有未设置的位可以变为设置，而设置的位永远不会再变为未设置。
  • 因此 dp[i] 最多包含 30 个元素。

解题思路

这道题的核心思路是利用按位 OR 运算的单调性质。

关键观察：

  1. 对于任意位置 i，以 i 结尾的所有子数组的 OR 值集合大小最多为 30（因为整数最多有 30 个二进制位）
  2. 当我们从右到左扩展子数组时，OR 值只能增大或保持不变（位运算的单调性）
  3. 一旦某个位被设置为 1，它就永远不会变回 0

动态规划思路：

  • 维护 dp[i] 表示所有以位置 i 结尾的子数组的 OR 值集合
  • 对于位置 i+1，我们可以通过以下方式构建 dp[i+1]：
    • 包含单独的 nums[i+1]
    • 将 nums[i+1] 与 dp[i] 中的每个值进行 OR 运算

优化： 由于 OR 运算的单调性，dp[i] 的大小被限制在常数级别（最多 30），这使得算法的时间复杂度可控。

算法步骤：

  1. 初始化结果为 |k - nums[0]|
  2. 对每个位置 i，维护以该位置结尾的所有可能 OR 值
  3. 对于每个 OR 值，计算与 k 的差值并更新最小值
  4. 利用去重优化存储空间

代码实现

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        int result = abs(k - nums[0]);
        
        vector<int> dp = {nums[0]};
        
        for (int i = 1; i < n; i++) {
            vector<int> new_dp = {nums[i]};
            result = min(result, abs(k - nums[i]));
            
            for (int val : dp) {
                int or_val = val | nums[i];
                new_dp.push_back(or_val);
                result = min(result, abs(k - or_val));
            }
            
            sort(new_dp.begin(), new_dp.end());
            new_dp.erase(unique(new_dp.begin(), new_dp.end()), new_dp.end());
            dp = move(new_dp);
        }
        
        return result;
    }
};

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        result = abs(k - nums[0])
        
        dp = {nums[0]}
        
        for i in range(1, n):
            new_dp = {nums[i]}
            result = min(result, abs(k - nums[i]))
            
            for val in dp:
                or_val = val | nums[i]
                new_dp.add(or_val)
                result = min(result, abs(k - or_val))
            
            dp = new_dp
        
        return result

public class Solution {
    public int MinimumDifference(int[] nums, int k) {
        int n = nums.Length;
        int result = Math.Abs(k - nums[0]);
        
        HashSet<int> dp = new HashSet<int> { nums[0] };
        
        for (int i = 1; i < n; i++) {
            HashSet<int> newDp = new HashSet<int> { nums[i] };
            result = Math.Min(result, Math.Abs(k - nums[i]));
            
            foreach (int val in dp) {
                int orVal = val | nums[i];
                newDp.Add(orVal);
                result = Math.Min(result, Math.Abs(k - orVal));
            }
            
            dp = newDp;
        }
        
        return result;
    }
}

var minimumDifference = function(nums, k) {
    const n = nums.length;
    let result = Math.abs(k - nums[0]);
    
    let dp = new Set([nums[0]]);
    
    for (let i = 1; i < n; i++) {
        const newDp = new Set([nums[i]]);
        result = Math.min(result, Math.abs(k - nums[i]));
        
        for (const val of dp) {
            const orVal = val | nums[i];
            newDp.add(orVal);
            result = Math.min(result, Math.abs(k - orVal));
        }
        
        dp = newDp;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n × 30) = O(n)，其中 n 是数组长度。每个位置最多维护 30 个不同的 OR 值
空间复杂度O(30) = O(1)，dp 集合最多包含 30 个元素

相关题目