2021년 3월 LeetCoding Challenge — 2일 차: 불일치 설정

문제 설명

원래 1에서 n까지의 모든 숫자를 포함하는 일련의 정수 s가 있습니다. 불행히도 일부 오류로 인해 s의 숫자 중 하나가 세트의 다른 숫자로 복제되어 한 숫자가 반복되고 다른 숫자가 손실됩니다.

오류 후 이 세트의 데이터 상태를 나타내는 정수 배열 nums가 제공됩니다.

두 번 나오는 숫자와 빠진 숫자를 찾아 배열 형태로 반환합니다.

예 1:

**Input:** nums = [1,2,2,4]
**Output:** [2,3]

예 2:

**Input:** nums = [1,1]
**Output:** [1,2]

해결책

따라서 문제에서 배열에서 누락되고 반복되는 숫자를 찾아야 합니다. 여기서 우리는 문제를 해결하기 위한 2가지 접근법에 대해 논의할 것입니다.

접근법 1 — 정렬: 처음에는 배열을 정렬하고 누락되거나 반복되는 숫자를 찾을 수 있습니다. 누락된 숫자를 확인하기 위해 인접한 두 숫자의 차이를 찾습니다. 1보다 크면 누락된 숫자는 두 숫자 사이의 숫자가 됩니다. 반복되는 숫자를 찾기 위해 인접한 두 숫자가 같은지 확인합니다. 그들이 같으면 반복되는 숫자를 찾은 것입니다.

배열에 값을 저장하고 반환합니다.

시간 복잡도: O(nlogn), 배열을 정렬하려면 nlogn 시간이 필요함

공간 복잡도: O(1)

접근법 2 — HashMap: HashMap에 숫자의 빈도를 저장할 수 있습니다. 또 다른 반복에서는 1에서 n으로 이동하여 발생을 확인합니다. 숫자의 발생이 2이면 해당 숫자가 반복되고 해시맵에 없으면 누락된 숫자입니다.

시간 복잡도: O(n)

공간 복잡도: O(n)

여기에서 코드를 찾을 수 있습니다