【Leetcode 每日一题 - 扩展】3171. 找到按位或最接近 K 的子数组

问题背景

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

数据约束

• $1\le nums.length\le 10^5$
• $1\le nums[i]\le 10^9$
• $1\le k\le 10^9$

解题过程

这题是对数组元素进行某种操作后按照某种标准求子数组的模板题，这类问题的特点就是通常要求的操作没有逆运算，例如这里的或运算，它的逆运算是不容易实现的。
解决方案有两个，一是使用 LogTrick，找了一圈没找到出处在哪里，那还是贴一下 灵神题解。大体上思路是在嵌套循环的基础上，跳过明显不可能是结果的情形，有点像剪枝。在这题中，如果循环中遇到的新元素没能增加运算结果，那它也不可能在更大范围内产生不同的情形，可以跳出内层循环。
这种做法，可以将时间复杂度从 $O(N^2)$ 优化到 $O(NlogU)$，其中 $U$ 是数组中的最大值。

另一种思路当然是滑窗，需要解决元素排除出窗口这个操作的实现，实际上用到了类似栈的思想，数组 $nums[i]$ 记录的是 $nums[i]|nums[i-1]...|nums[0]$ 的结果。
多定义一个变量 $bottom$，避免不必要的数据更新操作。

具体实现

LogTrick

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            res = Math.min(res, Math.abs(cur - k));
            // 和暴力解的区别就在于多进行了一个判断，去掉了不必要的遍历
            for(int j = i - 1; j >= 0 && (nums[j] | cur) != nums[j]; j--) {
                nums[j] |= cur;
                res = Math.min(res, Math.abs(nums[j] - k));
            }
        }
        return res;
    }
}

滑动窗口

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        int bottom = 0;
        int rightOr = 0;
        for(int left = 0, right = 0; right < nums.length; right++) {
            // 元素从窗口右侧进入
            rightOr |= nums[right];
            while(left <= right && (nums[left] | rightOr) > k) {
                // 循环条件保证了 (nums[left++] | rightOr) 大于 k，相应地更新结果
                res = Math.min(res, (nums[left++] | rightOr) - k);
                // bottom 始终指向栈底，它在窗口之外表示 rightOr 的结果没有被 nums 数组记录
                if(bottom < left) {
                    // 遍历并把结果更新到 nums 数组中
                    for(int i = right - 1; i >= left; i--) {
                        nums[i] |= nums[i + 1];
                    }
                    // 更新栈底指针
                    bottom = right;
                    // 重置右侧或运算结果
                    rightOr = 0;
                }
            }
            // 内层循环结束，表示 left <= right 或 (nums[left] | rightOr) > k 条件被打破
            if(left <= right) {
                // 循环条件保证了 k 大于 (nums[left++] | rightOr)，在合法的情况下更新结果
                res = Math.min(res, k - (nums[left] | rightOr));
            }
        }
        return res;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/145182314

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！