정렬된 이진 배열에서 1을 세는 자바스크립트 프로그램

정렬된 이진 배열에서 1을 계산하는 두 가지 방법이 있습니다. 첫 번째는 배열을 반복하고 1의 수를 계산하는 것입니다. 두 번째 방법은 이진 검색 알고리즘을 사용하여 배열에서 처음으로 나타나는 1을 찾는 것입니다.

이러한 방법을 사용하려면 배열을 정렬해야 한다는 점에 유의하는 것이 중요합니다.

이 블로그 게시물에서는 정렬된 이진 배열에서 1의 개수를 계산하는 JavaScript 프로그램에 대해 설명합니다. 또한 프로그램을 보다 효율적으로 만들기 위한 몇 가지 극단적인 경우와 최적화 기술을 살펴보겠습니다.

문제 설명

정렬된 이진 배열이 주어지면 작업은 배열에 있는 1의 수를 세는 것입니다. 배열의 크기는 제한되지 않으며 해당 요소는 0 또는 1만 될 수 있습니다.

들어가세요

으아악

출력

으아악

방법 1

가장 먼저 생각나는 접근 방식은 배열을 반복하고 1의 개수를 세는 것입니다.

• 카운트 변수를 초기화하여 숫자를 배열에 저장합니다.

• 배열을 반복하고 각 요소를 확인하세요. 현재 요소가 1과 같으면 카운터를 증가시킵니다.

예

으아악

그러나 이 접근 방식의 시간 복잡도는 O(n)입니다. 여기서 n은 배열의 크기입니다. 전체 배열을 한 번 반복하기 때문입니다.

이는 배열이 정렬되어 있다는 점을 활용하여 최적화할 수 있습니다.

방법 2

배열에서 1의 첫 번째 인스턴스를 찾으려면 이진 검색 방법을 사용하세요. 배열의 총 항목 수에서 첫 번째 1 인스턴스의 인덱스를 빼면 1의 수를 얻을 수 있습니다.

• 이 구현에서는 "첫 번째 발생" 이진 검색 기술을 사용하여 배열에서 0의 첫 번째 인스턴스를 찾습니다.

• 낮은 변수와 높은 변수는 처음에 배열의 첫 번째와 마지막 인덱스로 설정됩니다.

• 배열의 항목 수는 숫자 1의 첫 번째 인스턴스 인덱스를 기록하는 데 사용되는 firstOne이라는 변수의 값으로도 지정됩니다.

• while 루프는 낮은 인덱스가 높은 인덱스보다 크거나 같을 때까지 계속 실행됩니다. 각 반복 후에 현재 범위의 중간점을 결정합니다.

• 중간 요소가 1인 경우 firstOne 변수를 업데이트하고 높은 인덱스를 이전 요소로 이동합니다. 중간점의 요소가 0이면 낮은 인덱스를 다음 요소로 이동합니다.

• while 루프가 완료된 후 첫 번째 변수가 배열의 -1 값에 해당하는지 확인합니다. 그렇다면 배열에 1이 없다는 의미이므로 1이 반환됩니다. 그렇지 않은 경우 firstOne에서 arr.length를 뺀 값을 반환합니다.

예

으아악

이 방법의 시간 복잡도는 O(log n)로, 이전 방법보다 훨씬 효율적입니다.

이 튜토리얼에서는 정렬된 이진 배열에서 1의 개수를 계산하는 JavaScript 프로그램에 대해 논의했습니다.

위 내용은 정렬된 이진 배열에서 1을 세는 자바스크립트 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!