K 인덱스만큼 시계 반대 방향으로 배열을 회전하는 범위 합계 쿼리용 JavaScript 프로그램

배열의 반시계 방향 회전은 주어진 배열의 모든 요소를 ​​지정된 인덱스 수만큼 왼쪽으로 회전하는 것을 의미합니다. 이 기사에서는 k 인덱스만큼 시계 반대 방향으로 배열을 회전하는 범위 합계 쿼리에 대한 JavaScript 프로그램을 구현합니다.

문제 소개

이 문제에는 몇 가지 정수를 포함하는 배열과 쌍 형태의 값을 포함하는 또 다른 배열이 제공됩니다. 각 쌍은 현재 쿼리에 필요한 회전 수입니다. 주어진 회전 수 후에 우리는 범위를 얻고 해당 범위에 있는 요소의 합계에 답해야 합니다. 예를 들어

예 1

으아아아

지침

회전 횟수는 3이므로 3번 회전한 후의 배열은 4 5 6 1 2 3입니다.

1~4 범위의 요소는 5, 6, 1, 2입니다. 따라서 총합은 14입니다.

예 2

으아아아

지침

회전 횟수는 8이므로 8회전 후의 배열은 8%(배열 길이) 회전과 같습니다. 배열 회전의 길이 이후에는 동일한 배열이 다시 나타나기 때문에 8회전은 2회전과 같습니다.

그러므로 8번 회전한 배열은 3 4 5 6 1 2입니다.

이 범위에서 0~3개의 요소는 각각 3, 4, 5, 6입니다. 따라서 합은 18이다.

순진한 방법

간단한 접근 방식에서는 배열 쿼리에 설명된 모든 단계를 간단히 수행합니다. 마찬가지로 배열을 회전시킨 다음 배열 요소를 지정된 횟수만큼 회전한 다음 범위에 있는 요소의 합을 확인합니다. 코드를 살펴보겠습니다 -

예

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(Q*N)입니다. 여기서 Q는 쿼리 수이고 N은 배열 크기입니다.

위 코드의 시간 복잡도는 O(N)입니다. 왜냐하면 크기가 N인 새로운 배열을 생성하기 때문입니다.

접두사 합계 방법

prefix sum 메서드에서는 prefix sum 배열을 생성하고 prefix sum 배열의 각 인덱스에는 현재 인덱스까지의 모든 요소의 합계가 포함됩니다. 코드를 살펴보겠습니다 -

예

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(Q)입니다. 여기서 Q는 쿼리 수입니다.

위 코드의 시간 복잡도는 O(N)입니다. 왜냐하면 배열 요소의 접두어 합계를 저장하기 위해 새 배열을 생성하기 때문입니다.

결론

이 튜토리얼에서는 k 인덱스만큼 시계 반대 방향으로 배열을 회전하는 범위 합계 쿼리용 JavaScript 프로그램을 구현했습니다. 배열을 시계 반대 방향으로 회전한다는 것은 주어진 배열의 모든 요소를 ​​지정된 인덱스 수만큼 왼쪽으로 회전하는 것을 의미합니다. 우리는 먼저 두 가지 방법, 즉 시간 복잡도가 O(Q*N)인 순진한 방법과 시간 복잡도가 O(Q)인 접두사 합계 방법을 구현했습니다.

위 내용은 K 인덱스만큼 시계 반대 방향으로 배열을 회전하는 범위 합계 쿼리용 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!