3097 - Shortest Subarray With OR at Least K II

題目

Find the shortest subarray of $A$ s.t. the or of the element in the subarray is nto smaller that $K$.

Output: length of the shortest subarray.

$A_i\le {10}^9$$|A|\le {10}^5$

想法

考慮到假如 [l, r] 區段 Or 起來會 $\ge K$，那 [l-1, r], [l, r+1] 也同樣會滿足條件。

所以我們可以用 Sliding Window 的方式尋找滿足條件的最小區間。

Code

struct OrSet {
    int v = 0;
    array<int, 32> tab = {0};

    void insertD(int x, int d) {
        for (int i = 0; i < 32; ++i) {
            if (x & (1 << i)) {
                tab[i] += d;
            }
        }
    }

    void insert(int x) {
        insertD(x, 1);
    }

    void remove(int x) {
        insertD(x, -1);
    }

    int get() const {
        int r = 0;
        for (int i = 0; i < 32; ++i) {
            if (tab[i]) {
                r |= 1 << i;
            }
        }
        return r;
    }
};

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        OrSet v;
        size_t ans = nums.size() + 1;
        for (size_t l = 0, r = 0; r < nums.size(); ++r) {
            v.insert(nums[r]);
            while (v.get() >= k && l <= r) {
                ans = min(ans, r - l + 1);
                v.remove(nums[l]);
                ++l;
            }
        }

        if (ans == nums.size() + 1) {
            return -1;
        }

        return ans;
    }
};

Changelog

Last edited 2 days ago

View full history

c6b9058-Update