AP를 구성하는 모든 트리플을 정렬된 배열로 인쇄하는 JavaScript 프로그램

AP는 연속된 두 요소의 차이가 항상 동일한 산술 수열입니다. 순진한 방법, 이진 검색 방법 및 2포인터 방법의 세 가지 방법을 사용하여 AP를 형성하는 정렬된 배열의 모든 트리플을 인쇄합니다.

문제 소개

이 질문에서 우리는 정렬된 배열을 얻습니다. 이는 모든 요소가 증가하는 형식임을 의미합니다. 배열에서 세 가지 요소를 찾아 AP를 구성해야 합니다. 예를 들어 -

주어진 배열: 1 5 2 4 3

주어진 배열에서 인접한 요소 간의 차이가 동일하므로 1 2 3과 5 4 3이라는 두 개의 트리플이 있습니다. 또한 작성된 대로 트리플만 찾으면 되므로 더 긴 시퀀스를 찾을 수 없습니다.

트리플을 찾는 방법을 살펴보겠습니다. -

방법

순진한 방법

이 방법에서는 루프를 사용하여 배열 위로 이동하고 각 반복마다 현재 인덱스에 비해 더 많은 수의 다른 배열을 실행합니다. 그런 다음 첫 번째 중첩 배열 내에 다시 중첩 배열을 구현하여 AP를 구성할 수 있는 요소를 찾습니다. 코드를 살펴보겠습니다 -

예

으아악

위 코드의 시간 복잡도는 O()입니다. 여기서 N은 배열의 크기입니다.

위 코드의 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.

간단한 방법을 따라해 보세요

이전 방법에서는 두 개의 요소가 있을 때 공통 차이점이 있기 때문에 세 번째 요소를 찾을 수 있으므로 세 번째 요소를 찾으려면 선형 검색을 사용하는 대신 이진 검색을 사용하고 위 코드의 시간 복잡도를 줄일 수 있습니다. -

예

으아악

위 코드의 시간 복잡도는 O()입니다. 여기서 N은 배열의 크기입니다.

위 코드의 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.

효율적인 방법

이 방법에서는 두 개의 포인터를 사용하여 현재 위치와 동일한 차이가 있는 요소를 찾습니다. 코드를 살펴보겠습니다 -

예

으아악

위 코드의 시간 복잡도는 O(N*N)입니다. 여기서 N은 주어진 배열의 크기이고 위 방법의 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다. p>

참고 - 처음 두 방법은 모든 유형의 정렬 또는 정렬되지 않은 배열에 유효하지만 마지막 방법은 정렬된 배열에만 적용됩니다. 배열이 정렬되지 않은 경우 정렬할 수 있지만 이 방법이 여전히 가장 좋습니다. 다른 사람.

결론

이 튜토리얼에서는 주어진 정렬 배열에서 AP를 형성하는 모든 트리플을 인쇄하는 JavaScript 프로그램을 구현했습니다. Ap는 연속된 두 요소의 차이가 항상 같은 수열입니다. 우리는 세 가지 방법을 살펴보았습니다: 시간 복잡도가 O(N*N*N)인 순진한 방법, 시간 복잡도가 O(N*N*log(N))인 이진 검색 방법, 2포인터 방법.

위 내용은 AP를 구성하는 모든 트리플을 정렬된 배열로 인쇄하는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!