[LeetCode] Contains Duplicate II 파이썬 (dict)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        seen = {}
        
        for idx, value in enumerate(nums):
            if value not in seen:
                seen[value] = [idx]
            else:
                seen[value] += [abs(idx - seen[value][-1])]

        for key in seen.keys():
            if len(seen[key])>1:
                if sum( [x<=k for x in seen[key][1:]] ) > 0:
                    return True
        return False

seen 이라는 dict를 만들어서 value 들은 list 형식으로 추가해서

duplicate일 경우(seen에 있는 key일 경우) 현재 위치 - 기존의 가장 최근 위치[-1]를 계산해 준다음 value에 넣어준다

 

이렇게 모든 list에 있는 원소들을 seen에 넣어주면

예제 2번 의 경우

nums = [1,0,1,1]; k = 1 일때

seen의 dict의 모습은 이렇게 나온다

duplicate가 아닌, 즉 seen의 value인 리스트의 길이가 1보다 큰경우 (2개 이상의 원소가 있을 경우 non-duplicate),

에만 k에 대한 조건이 해당되는 경우가 있는 지만 체크하면 된다.

 

duplicate일 경우 처음 원소를 제외하고 나머지 원소들 중에서 x <= k 인지를 T/F로 list comprehension으로 사용해서 sum 계산을 해주고 0 보다 크다면 (1번 이라도 k보다 작거나 같은 경우가 존재할 경우 True 리턴하고 seen을 다 순회했는데도 없다면 False 리턴

 

---

축약된 코드 O(n)번만 계산한다

dict에 넣는 과정과 k조건을 계산하는 것을 한번에 처리. dict의 value를 리스트로 넣지않고 update만 시켜줬다

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        dic = {}
        for i, v in enumerate(nums):
            if v in dic and i - dic[v] <= k:
                return True
            dic[v] = i
        return False

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {boolean}
    def containsNearbyDuplicate(self, nums, k):
        lookup = {}
        for i, num in enumerate(nums):
            if num not in lookup:
                lookup[num] = i
            else:
                # It the value occurs before, check the difference.
                if i - lookup[num] <= k:
                    return True
                # Update the index of the value.
                lookup[num] = i
        return False