[Week 6-2] 🔥特集講座2日目

6269 ワード
ブスターキャンプ アルゴリズム#アルゴリズム# テキストリンク
第6週水曜日
  • 個人学習(パスワードチャレンジ)

    • [LeetCode 645. Set Mismatch]


    1からnまでの自然数を含むリストで、2つのエントリ数とゼロのエントリ数を検索して返します.
    Input: nums = [1,2,2,4]
Output: [2,3]

Input: nums = [1,1]
Output: [1,2]
  • アクセス
    リストには1からnまでの数字が含まれている必要があるので、リストの長さ=nです.
    欠落した数値を検索するには、指定されたリストをsetに変更して、set(1~n)との差セットを求めます.
    重複する数を検索するには...?まずは繰り返し
    時間複雑度:O(n)
  • コード
    • from collections import defaultdict
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N = len(nums)
        origin = set(range(1,N+1))
        
        [missed] = origin - set(nums)
        duplicated = -9999
        
        dct = defaultdict(bool)
        for n in nums:
            if dct[n]:
                duplicated = n
                break
            
            dct[n] = True

        return [duplicated, missed]

    もっと良い方法はありませんか?
    繰り返しの数を求めるときは、繰り返す必要はなく、より優雅に求めることができるようです.
    思いがけない方法
    ご利用に!1からnまでの総和でset(num)(重複が解消された)の総和を外すと、numで欠落した数字を求めることができる.
    2番の数字を求めるときは、numの合計からset(num)の合計を減算すればよい.
    時間の複雑さはO(N)ですが、もっとクールです... 
    참고)

멀쩡 : [1, 2, 4, 3, 5]
num : [1, 2, 2, 3, 5]
set : [1, 2,   3, 5]
    class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N = len(nums)
        total = (N * (N+1)) // 2  # 1~n까지 다 멀쩡한 경우
        missing = total - sum(set(nums))
        duplicate = sum(num) - sum(set(nums))
        return [duplicate,missing]
    [WEB #12] SPA vs MPA, CSR vs SSR
    Spark関連環境問題及び解決方法の記録