主題

LeetCode - 1819. Number of Different Subsequences GCDs 解題心得

Not In My Back Yard | 2021-09-19 00:00:01 | 巴幣 0 | 人氣 28

題目連結:


題目意譯:
你被給定一陣列 nums 其由正整數組成。

一個數字序列的 GCD 定義為最大整數其可整除序列中所有數字。

例如,數列 [4,6,16] 的 GCD 為 2。

一陣列的一個子序列為一序列其可由移除陣列中若干個(可能沒有)個元素而產生。

例如,[2,5,10] 為 [1,2,1,2,4,1,5,10] 的一個子序列。

回傳所有 nums 的非空子序列的相異 GCD 之值數量。

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



範例測資:
範例 1:
輸入: nums = [6,10,3]
輸出: 5
解釋: 附圖顯示了所有非空子序列以及它們的 GCD 之值。
相異的 GCD 之值為 6 、 10 、 3 、 2 和 1。

範例 2:
輸入: nums = [5,15,40,5,6]
輸出: 7


解題思維:
(以下假設我們知道如何取一數列的 GCD 之值,如果不曉得的話可以參見輾轉相除法之維基頁面
首先我們可以觀察得到:
一:當已知一數列的 GCD 值為 G 時,就算往數列加再多的數字進去 G 的值只會變小和不變,不會變大;
二:而如果原本數列之 GCD 之值為 G ,則我們加入任意 G 的倍數之數字則不會改變整個數列的 GCD 之值(依然是 G)。

假設 nums 中最大的數字值為 M,則根據觀察到的現象一可知最大的 GCD 之值絕對不可能會超過 M。且令布林陣列 H 用來儲存某數字是否存在於 nums 中,因此對於每個 nums[i] 我們令 H[nums[i]] 設為真(代表 nums[i] 存在於 nums 中)。

接著我們窮舉所有可能的 GCD 之值,從 1 開始跑到 M ,每個值都去判斷可不可以從 nums 中產生。

至於判斷方式則要依據觀察到的現象之二,因此對於現在要判斷的 GCD 之值 G ,我們窮舉出 G 、 2G 、 3G …… 之值並篩選出有出現於 nums 中的數字(藉由 H 來篩選)。然後我們將篩選出的數字(如果有的話)全部取其 GCD 之值。如果這些數字的 GCD 恰好為 G ,則表示我們可以藉由 nums 中的這些數字生出 G。

而過程中所有可以產生出來的 G 值之數量即為所求。




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

創作回應

相關創作

更多創作