程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Subsets II

LeetCode Subsets II

編輯:C++入門知識

LeetCode Subsets II


LeetCode解題之Subsets II


原題

羅列出一個包含重復數字的集合的所有的子集。

注意點:

子集中的元素需要按照不降序排列 結果集中不能重復

例子:

輸入: nums = [1,2,2]

輸出:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解題思路

在 Subsets 迭代版本的基礎上思考。在迭代重復元素的時候會生成重復的結果,那麼在迭代重復元素時要特殊處理一下。就拿[1,2,2]來說,在迭代完1之後結果集為[[], [1]],迭代第一個2後,[[], [1], [2], [1,2]],接下來就要迭代重復的元素2了,此時如果遍歷在迭代第一個2之前就存在的結果集元素([[], [1]])時,就會產生重復,我們只能在上一輪迭代產生的新的結果中繼續添加。所以要一個額外的變量來表示在結果集中的哪個位置開始遍歷。

AC源碼

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        nums.sort()
        temp_size = 0
        for i in range(len(nums)):
            start = temp_size if i >= 1 and nums[i] == nums[i - 1] else 0
            temp_size = len(result)
            for j in range(start, temp_size):
                result.append(result[j] + [nums[i]])
        return result


if __name__ == "__main__":
    assert Solution().subsetsWithDup([1, 2, 2]) == [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved