•
문제 링크 : leetcode.com
•
문제 설명 : 제공되는 숫자 배열 중, 조건에 따라 존재하지 않는 숫자나 중복된 숫자를 리스트에 설정하여 반환
•
풀이 방법
◦
존재하는 숫자를 별도의 해시 테이블에 저장하는 방식을 사용
•
시간복잡도 :
•
성공 코드
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
include_key = set()
result = []
for num in nums:
if num in include_key:
result.append(num)
include_key.add(num)
exclude_key = set([i for i in range(1, len(nums) + 1)]) - include_key
result.extend(list(exclude_key))
return result
Python
복사
•
정렬을 사용한 성공코드(O(NlogN))
다른 솔루션을 확인해보니, return하는 값은 2가지만 존재하면 되는 것이었다.
즉, 중복 숫자는 하나만 있고 미 존재 숫자도 하나만 있는 것이었다.
아래와 같이 정렬 후 순회하면서, 중복 숫자 / 미 존재 숫자를 따로 구해서 반환해도 된다.
class Solution:
def findErrorNums(self, nums):
nums.sort()
duplicate = -1
missing = 1 # 초기값으로 1 설정
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
duplicate = nums[i]
elif nums[i] > nums[i - 1] + 1:
missing = nums[i - 1] + 1
if nums[-1] != len(nums):
missing = len(nums)
return [duplicate, missing]
Python
복사
