주어진 쿼리에 따라 배열 요소를 재정렬하고 업데이트합니다.

이 질문에서는 배열 요소에 대해 주어진 쿼리를 실행합니다. 쿼리에는 왼쪽 회전, 오른쪽 회전 및 배열 요소 업데이트의 루프가 포함되어 있습니다.

문제 해결의 논리적인 부분은 배열 회전입니다. 배열을 왼쪽으로 회전하는 간단한 방법은 각 요소를 다음 요소로 바꾸고 마지막 요소를 첫 번째 요소로 바꾸는 것입니다.

deque 데이터 구조를 사용하여 배열을 효율적으로 회전할 수 있습니다.

문제 설명 -정수 값을 포함하는 arr[] 배열이 제공됩니다. 추가적으로, K개의 쿼리를 포함하는 요청[] 배열이 제공됩니다. 다음 규칙에 따라 arr[] 배열 요소에 대해 요청[]에 제공된 각 쿼리를 실행해야 합니다.

• {0} - 배열에서 원형 왼쪽 회전을 수행합니다.

• {1) - 배열의 오른쪽 원형 회전을 수행합니다.

• {2, p, q} - 인덱스 p의 요소를 q로 업데이트합니다.

• {3, p} - 인덱스 p에 있는 요소를 인쇄합니다.

예

들어가세요

으아아아

출력

으아아아

설명- 각 쿼리를 실행해 보겠습니다.

• {1} -> 배열을 오른쪽으로 회전하면 배열은 {51, 8, 9, 13, 44, 76, 67, 21}

이 됩니다.

• {0} -> 업데이트된 배열을 왼쪽으로 회전한 후 배열은 {8, 9, 13, 44, 76, 67, 21, 51}과 동일해집니다.

• {2, 4, 50} -> 인덱스 4의 요소를 50으로 업데이트하면 배열은 {8, 9, 13, 44, 50, 67, 21, 51}

  이 됩니다.

• {3, 2} -> 두 번째 인덱스의 요소를 인쇄합니다.

• {2, 2, 223}−> 두 번째 인덱스의 요소를 223으로 업데이트하면 배열은 {8, 9, 223, 44, 50, 67, 21, 51}이 됩니다. p>

• {3, 2} -> 두 번째 인덱스의 요소를 인쇄합니다.

들어가세요

으아아아

출력

으아아아

Description- 2번째와 0번째 인덱스부터 배열을 출력합니다.

들어가세요

으아아아

출력

으아아아

설명- 배열을 오른쪽으로 2번 회전하면 배열은 [51, 78, 76, 20]이 됩니다. 첫 번째 인덱스의 요소는 78입니다.

방법 1

이 방법에서는 각 쿼리를 반복하고 주어진 쿼리를 기반으로 작업을 수행합니다. 배열의 각 요소를 다음 요소로 교체하여 왼쪽으로 회전하고, 각 요소를 이전 요소로 교체하여 오른쪽으로 회전합니다.

알고리즘

1단계- 각 쿼리를 반복하면서 시작합니다.

2단계− query[p][0]이 0인 경우 다음 단계를 따르세요.

2.1단계- 배열의 첫 번째 요소를 사용하여 "temp" 변수를 초기화합니다.

2.2단계- 배열 순회를 시작하고 각 요소를 다음 요소로 바꿉니다.

2.3단계- 마지막 요소를 "temp" 값으로 바꿉니다.

3단계− query[p][0]이 1이면 다음 단계를 따르세요.

3.1단계- 배열의 마지막 요소를 "temp" 변수에 저장합니다.

3.2단계- 배열 순회를 시작하고 각 요소를 이전 요소로 바꿉니다.

3.3단계- 첫 번째 요소를 "temp" 값으로 업데이트합니다.

4단계- 요청[p][0]이 2인 경우, 주어진 인덱스의 배열 요소를 주어진 값으로 업데이트합니다.

5단계- 요청[p][0]이 3이면 주어진 인덱스의 배열 값을 인쇄합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N*K), 쿼리를 순회하고 배열을 회전합니다.

공간 복잡도 - O(1) 왜냐하면 우리는 일정한 공간을 사용하기 때문입니다.

방법 2

이 방법에서는 deque를 사용하여 배열 요소를 저장합니다. 그런 다음 배열을 왼쪽으로 회전하려면 대기열에서 이전 요소를 팝하고 대기열의 끝으로 푸시하면 됩니다. 마찬가지로 배열을 올바른 방향으로 회전할 수 있습니다.

알고리즘

1단계- deque를 정의하고 모든 배열 요소를 대기열에 푸시합니다.

2단계- for 루프를 사용하여 각 쿼리를 반복합니다.

3단계- 배열을 왼쪽으로 회전하려면 대기열 시작 부분에서 첫 번째 요소를 제거하고 대기열 끝으로 푸시합니다.

4단계- 배열을 올바른 방향으로 회전하려면 대기열 끝에서 요소를 제거하고 해당 요소를 시작 부분으로 푸시합니다.

5단계- 주어진 쿼리를 기반으로 요소를 업데이트하거나 요소 값을 인쇄합니다.

예

으아아아

출력

으아아아

시간 복잡도 - 배열 요소를 대기열에 삽입하는 경우 O(N+K)입니다.

공간 복잡성 - 요소를 데크에 저장하기 위한 O(N)입니다.

deque 데이터 구조를 사용하면 O(1) 시간에 왼쪽 및 오른쪽 회전 작업을 수행할 수 있습니다. 따라서 특정 쿼리를 실행하는 코드의 효율성이 향상됩니다.

위 내용은 주어진 쿼리에 따라 배열 요소를 재정렬하고 업데이트합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!