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

第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]