OR 至少 K II 的最短子數組

3097。 OR 至少 K II 的最短子數組

難度：中

主題：陣列、位元操作、滑動視窗

給你一個由非負整數組成的陣列nums和一個整數k。

如果一個陣列的所有元素按位或至少 k.，則該數組稱為特殊

傳回最短特殊非空子數組¹nums的長度，如果不存在特殊子數組則回傳-1。

範例1：

• 輸入： nums = [1,2,3], k = 2
• 輸出： 1
• 解釋： 子數組 [3] 的 OR 值為 3。因此，我們返回 1。

範例2：

• 輸入： nums = [2,1,8], k = 10
• 輸出： 3
• 解釋： 子數組 [2,1,8] 的 OR 值為 11。因此，我們返回 3。

範例 3：

• 輸入： nums = [1,2], k = 0
• 輸出： 1
• 解釋： 子數組 [1] 的 OR 值為 1。因此，我們返回 1。

約束：

• 1 5
• 0 9
• 0 9

提示：

1. 對於每個nums[i]，我們可以維護以它結尾的每個子數組的按位或結果。
2. 按位或的特性是它永遠不會取消設定任何位，而只會設定新位
3. 因此每個 nums[i] 的不同結果數最多為 32 位元。

解：

我們可以使用滑動視窗方法結合位元操作來追蹤視窗中元素的 OR。

計劃：

1. 滑動視窗方法：使用兩個指標迭代數組，維護一個檢查 OR 值的子數組。
2. 位元或：OR 運算累加值。它永遠不會減少結果（即，一旦某個位元設為 1，就無法取消設定）。這意味著當我們擴展視窗時，OR 值只會增加或保持不變。
3. 效率：我們可以使用deque（雙端佇列）來維護子陣列的索引。這使我們能夠有效地滑動窗口，同時追蹤最小子數組長度。

步驟：

1. 遍歷數組，對於每個元素，維護一個運行的OR。
2. 對於每個元素，檢查 OR 是否超過或等於 k。如果是這樣，請嘗試從左側縮小視窗。
3. 應該透過追蹤雙端隊列結構中的 OR 值來有效地移動滑動窗口，以允許恆定時間滑動和收縮。

讓我們用 PHP 實作這個解：3097。 OR 至少 K II 的最短子數組

<?php
class Solution {
    const K_MAX_BIT = 30; // Maximum bit position we will check

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function minimumSubarrayLength($nums, $k) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $ors
     * @param $num
     * @param $count
     * @return int
     */
    private function orNum($ors, $num, &$count) {
        // Update the ors value and count bits that are set
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $ors
     * @param $num
     * @param $count
     * @return int
     */
    private function undoOrNum($ors, $num, &$count) {
        // Reverse the update on ors and count bits that are reset
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
$nums1 = [1, 2, 3];
$k1 = 2;
echo $solution->minimumSubarrayLength($nums1, $k1) . "\n"; // Output: 1

$nums2 = [2, 1, 8];
$k2 = 10;
echo $solution->minimumSubarrayLength($nums2, $k2) . "\n"; // Output: 3

$nums3 = [1, 2];
$k3 = 0;
echo $solution->minimumSubarrayLength($nums3, $k3) . "\n"; // Output: 1
?>

解釋：

1. 最小子數組長度方法:

   • 將 ans 初始化為不可能的高值 ($n 1)。
   • 使用兩個指標l（左）和r（右）來擴大和縮小視窗。
   • 在擴展視窗時使用 orNum 計算子數組的 OR，在縮小視窗時使用 undoOrNum 計算子數組的 OR。
   • 每當OR結果滿足或超過k時，檢查目前視窗大小是否小於ans。

2. orNum 和 undoOrNum 方法:

   • orNum 方法：透過更新計數數組將位元加入累積 OR 中。如果在視窗中新設定了一位（表示 count[i] 變為 1），則該位元將會新增至 ors 。
   • undoOrNum 方法：向左滑動視窗時，從累積 OR 中刪除位元。如果視窗中的任何數字中不再設定某個位元（表示 count[i] 變成 0），則該位元將從 ors 中刪除。

3. 時間複雜度:

   • 時間複雜度為 O(n)，因為每個索引最多在雙端佇列中新增和刪除一次。
   • n 是輸入數組的長度。

4*時間複雜度*:

• 儲存前綴OR數組和雙端佇列的空間複雜度為O(n)。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

1. 子數組：子數組是數組中連續的非空元素序列。  ↩

以上是OR 至少 K II 的最短子數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！