가장 작은 누락된 숫자를 찾는 JavaScript 프로그램

음수가 아닌 다양한 정수의 정렬된 배열을 얻었습니다. 여기서 누락된 가장 작은 숫자를 찾아야 합니다. 따라서 이 튜토리얼에서는 이 문제를 해결하는 다양한 방법을 탐색하고 다양한 예를 통해 시간 복잡도에 대해 논의합니다.

문제 이해하기

문제 설명은 매우 간단합니다. 음수가 아닌 다양한 정수의 정렬된 배열이 주어지면 그 배열에서 누락된 가장 작은 숫자를 찾아야 합니다. 이 문제를 이해하기 위해 예를 들어 보겠습니다.

예

배열 [1, 2, 4, 5, 6]이 있다고 가정합니다. 여기에서 이 배열의 숫자 2와 4 사이에 공백이 있음을 알 수 있습니다. 이러한 불일치는 숫자가 누락되었음을 나타냅니다. 이제 위치에 맞는 가장 작은 숫자를 찾아야 합니다.

숫자가 누락되었는지 확인하려면 먼저 배열에 숫자 3이 포함되어 있는지 확인해야 합니다. 숫자 3이 배열에 없으면 숫자 3이 배열에 포함되어 있지 않기 때문에 누락된 숫자라고 말할 수 있습니다.

이제 이 문제를 해결하는 몇 가지 방법을 살펴보겠습니다.

방법 1: 순진한 방법

이 문제를 해결하는 가장 쉬운 방법 중 하나는 배열을 반복하면서 각 항목이 올바른 위치에 있는지 확인하는 것입니다. 요소가 올바른 위치에 있지 않으면 누락된 요소의 최소 개수를 찾습니다.

예

위에서 설명한 코드입니다 -

으아아아

전체 배열을 반복하므로 이 방법의 시간 복잡도는 O(n)입니다.

그러나 이 솔루션은 정렬된 배열이 제공된다는 사실을 활용하지 않기 때문에 비효율적입니다.

방법 2: 이진 검색 방법

여기에서는 이 문제를 보다 효율적으로 해결하기 위해 이진 검색 방법을 사용하겠습니다. 이 방법에서는 배열에 없는 첫 번째 요소에 대해 이진 검색을 수행합니다. 이 메소드의 코드는 -

입니다.

예

으아아아

이진 검색을 수행하므로 위 방법의 시간 복잡도는 O(log n)입니다.

이 방법은 배열이 정렬된다는 점을 활용하므로 간단한 방법보다 더 효율적입니다.

방법 3: 선형 검색 방법

우리가 논의할 세 번째 방법은 선형 검색 방법입니다. 이 방법은 배열이 정렬되어 있다는 사실에 의존하며, 이를 통해 누락된 숫자를 식별하기 위해 선형 검색을 적용할 수 있습니다.

선형 검색 방법은 배열을 반복하고 각 멤버를 해당 인덱스와 비교하는 방식으로 작동합니다. 요소의 인덱스가 해당 값과 같지 않으면 누락된 요소는 해당 요소 앞의 배열 어딘가에 있습니다. 누락된 요소의 인덱스를 반환합니다.

예

선형탐색 방식의 코드는 다음과 같습니다 -

으아아아

전체 배열을 반복해야 하기 때문에 이 방법의 시간 복잡도는 O(n)입니다.

이 방법은 이진 검색 방법보다 효율성이 떨어지지만 작은 배열에 유용합니다.

방법 4: 향상된 이진 검색

우리가 논의할 네 번째 방법은 향상된 이진 검색 방법입니다. 이 방법은 중간 요소를 누락된 정수와 비교하는 대신 해당 인덱스와 비교한다는 점을 제외하면 이진 검색 방법과 매우 유사합니다.

수정된 이진 검색 방법의 기본 아이디어는 각 단계에서 배열을 반으로 나누고 중간 요소를 해당 인덱스와 비교하는 것입니다. 중간 요소가 해당 인덱스보다 큰 경우 누락된 멤버는 배열의 왼쪽 절반에 있어야 합니다. 중간 요소가 해당 인덱스보다 작거나 같으면 누락된 요소는 배열의 오른쪽 절반에 있어야 합니다.

예

수정된 이진 검색 방법의 코드 구현입니다. -

으아아아

이 방법의 시간 복잡도도 O(log n)로 이진 검색 방법과 동일합니다.

이 방법은 선형 검색 방법보다 효율적이며 배열 정렬이 필요합니다.

결론

이 블로그에서는 배열에서 누락된 가장 작은 숫자를 찾는 네 가지 방법에 대해 논의했습니다. 순진한 방법, 이진 탐색 방법, 선형 탐색 방법, 수정된 이진 탐색 방법이 있습니다.

위 내용은 가장 작은 누락된 숫자를 찾는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!