ETH官方钱包

前往
大廳
主題

LeetCode - 2568. Minimum Impossible OR 解題心得

Not In My Back Yard | 2024-01-20 12:00:24 | 巴幣 0 | 人氣 98

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的整數陣列 nums。

我們定義一整數 x 為「可被 nums 表示」,代表著存在著某些整數 0 ≦ index1 < index2 < …… < indexk < nums.length,滿足 nums[index1] | nums[index2] | …… | nums[indexk] = x。換句話說,一個整數為「可被表示」,代表著其可以被表示為 nums 中某個子序列的按位元 OR 之值。

回傳不可被 nums 表示的最小非零正整數。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [2,1]
輸出: 4
解釋: 1 和 2 已經存在於陣列中。我們知道 3 可被表示,因為 nums[0] | nums[1] = 2 | 1 = 3。由於 4 不可被表示,我們回傳 4。

範例 2:
輸入: nums = [5,3,2]
輸出: 1
解釋: 我們可以證明 1 是最小且不可被表示的數字。


解題思維:
可以看到所求必定是 2 的某個冪次。用反證法即可簡單證明:
    假設所求最小值不是 2 的某個冪次。而其二進位表示法中必定會至少有某一位的「1」不會出現在 nums 中的任何一個數字的對應位元中(否則該數應當能被表示)。而我們直接取這一位的「1」便可以得到 2 的某個冪次且更小並無法被表示。

    因此所求最小值必定是 2 的某個冪次。

那麼問題就變得很單純了——現在我們只需要找到最小且沒有出現在 nums 中的 2 的冪次即是所求。而作法很多樣,可以用陣列記錄哪些冪次出現過、可以排序後再掃過檢查、也可以只從 nums 中擷取出 2 的冪次並用位元遮罩表示哪些冪次出現(陣列的精簡版。範例程式碼即是使用這個方式)云云。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作