Find the Smallest Common Number

오름차순으로 정렬된 3개의 정수 배열에서 3개 배열 모두에 공통인 최소 수를 찾아야 합니다.

설명

오름차순으로 정렬된 3개의 정수 배열이 주어지고, 3개의 배열 모두에 공통되는 최소의 수를 찾는 알고리즘을 구현한다.

다음 세 가지 배열을 살펴 보겠습니다. 해는 6 으로, 모든 배열에 공통되는 최소수입니다.

팁

오름차순 배열을 활용한다.

3개의 포인터를 사용한다.

Solution

Runtime Complexity O(n)

Memory Complexity O(1)

해설

배열이 오름차순으로 정렬된다는 사실을 이용하는 방법을 생각해 봅시다.

세 개의 반복자(이터레이터)를 동시에 사용하여 각 배열을 스캔합니다.
각 배열의 최소치를 가지는 0 번째의 인덱스로부터 배열을 주사하는 것으로 시작됩니다.

세 개의 반복자가 가리키는 배열 인덱스의 값이 같으면,
모든 배열에 존재하는 최소값 (배열이 오름차순으로 정렬되어 있기 때문에)이 되기 때문에, 그 값을 돌려준다.

그렇지 않으면 세 점 중 가장 작은 값을 가리키는 반복자를 확인하십시오.
다음 인덱스를 가리키도록 그 반복자를 증가시킵니다.

세 개의 반복자 중 하나가 배열의 끝에 도달했을 때 공통 번호를 찾을 수 없으면 Null을 반환합니다.

구현

Test

Output