배열 요소 주파수 범위 쿼리를 위한 Javascript 프로그램

정수를 포함하는 배열과 쿼리를 포함하는 또 다른 배열을 얻습니다. 각 쿼리는 가장 왼쪽과 가장 오른쪽 인덱스와 배열의 한 요소로 제공되는 범위를 나타냅니다. 해당 범위 또는 하위 배열의 경우 해당 범위에서 특정 요소의 발생 빈도를 찾아야 합니다.

요소의 빈도는 범위에 있는 각 정수에 해당 요소가 몇 번 발생하는지 알려주어야 함을 의미합니다. 예를 들어 -

주어진 배열은 다음과 같습니다: [5, 2, 5, 3, 1, 5, 2, 2, 5]

쿼리 배열은 다음과 같습니다: [[0, 4, 5], [1, 7, 2]]

• 첫 번째 쿼리의 경우 하위 배열은 5, 2, 5, 3, 1이므로 5의 빈도는 2입니다.

• 두 번째 쿼리의 경우 하위 배열은 2, 5, 3, 1, 5, 2, 2이므로 2의 빈도는 3입니다.

방법

이 문제를 해결하려면 다음 단계를 따르세요. -

• 먼저, 각 쿼리를 호출하고 쿼리 요소를 매개변수로 전달하는 별도의 함수를 만듭니다.

• 함수 내에서 반복할 배열의 길이를 가져오고 주어진 요소의 빈도를 저장하기 위한 변수 개수를 생성합니다.

• for 루프를 사용하여 주어진 범위를 반복하고 각 반복마다 현재 배열 요소가 주어진 요소와 같으면 개수가 증가합니다.

• 마지막으로 주어진 요소의 현재 개수를 인쇄합니다.

예

더 나은 이해를 위해 위 단계를 구현하는 올바른 코드를 살펴보겠습니다. -

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(Q*N)입니다. 여기서 Q는 쿼리 수이고 N은 배열 크기입니다. 각 쿼리에 대해 주어진 범위 내의 배열을 반복하기 때문에 시간 복잡도는 N배입니다.

위 코드의 공간 복잡도는 O(1)입니다. 왜냐하면 아무것도 저장하기 위해 추가 공간을 사용하지 않기 때문입니다.

특별한 상황

위 코드에서는 O(Q*N)의 시간 복잡도를 얻습니다. 이는 주어진 배열에 존재하는 서로 다른 요소의 수가 각각에 대한 별도의 배열의 수보다 작을 경우 공간 복잡도를 계산하여 얻을 수 있습니다. 요소 시간 복잡성을 개선하거나 접두사 합계 매핑을 유지합니다.

그러나 이 방법은 많은 공간을 소비하고 복잡도는 O(D*N)입니다. 여기서 D는 배열에 존재하는 다양한 요소의 수이고 N은 배열의 길이입니다.

접두사 합계를 유지하면 모든 쿼리에 대한 답변이 O(1) 시간 내에 제공될 수 있으며 전체 시간 복잡도는 O(Q)가 됩니다. 여기서 Q는 쿼리 수입니다.

예

으아악

결론

이 튜토리얼에서는 각 쿼리에 제공된 범위에 있는 특정 요소의 빈도에 응답하기 위해 범위 쿼리에 응답하는 JavaScript 프로그램을 구현했습니다. 우리는 배열의 주어진 범위를 반복하고 개수를 얻기 위해 변수를 유지했습니다. 위 코드의 시간 복잡도는 O(Q*N)이고, 위 코드의 공간 복잡도는 O(1)입니다.

위 내용은 배열 요소 주파수 범위 쿼리를 위한 Javascript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!