前往
大廳
主題

LeetCode - 78. Subsets 解題心得

Not In My Back Yard | 2022-01-03 00:00:01 | 巴幣 10 | 人氣 201

題目連結:


題目意譯:
給定一個相異整數之陣列 nums,回傳所有可能的子集合(即冪集(Power Set))。

答案集合不得包含重複的子集合。可按任意順序回傳答案。

限制:
1 ≦ nums.length ≦ 10
-10 ≦ nums[i] ≦ 10
nums 中所有數字皆相異。



範例測資:
範例 1:
輸入: nums = [1,2,3]
輸出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

範例 2:
輸入: nums = [0]
輸出: [[],[0]]


解題思維:
假設 nums 中有 X 個元素,可以看到其冪集應當有 2 ^ X 個元素。而我們恰好可以利用二進位數字來窮舉每個元素挑與不挑之狀態。

例如 nums = [2,3,1] 因此 X = 3。而二進位數字 "101" 代表著要挑第 2 、 0 個元素也就是得到 [2,1] 、 "001" 代表著要挑第 0 個元素(陣列索引值時常從 0 開始,而最右邊的位元剛好是 2 ^ 0)即 [1] 等等。

因此我們從 i = 0 跑到 2 ^ X - 1,然後對於每個 i 值得出其所代表的子集合。將這些子集合包成一個陣列即是所求。




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

創作回應

工具人
好奇這種用bit的想法,跟用遞迴哪種比較快? (bit 複雜度是 O(2^n * n) ) 多了一個要遍歷每個位元的部分
2022-01-03 01:10:37
Not In My Back Yard
如果是單看複雜度的話,遞迴也是 O(2 ^ n * n) 喔
因為所有子集合的平均長度為 n / 2(也就是一半),所以光是把所有子集合放在答案陣列這件事情本身就至少需要 2 ^ n * (n / 2) 次存取。

而利用位元操作的好處是可以省略遞迴在記憶體堆疊段上所需要做的一些操作(記錄遞迴前的所有區域變數之情況等、遞迴後所有區域變數的值等),因為我們可以寫成迭代的版本。

而「通常」迭代版本的程式會比遞迴版本快上不少,尤其是這種窮舉子集合的情況更是如此。
2022-01-03 01:41:07

更多創作