C++로 작성된 배열의 오른쪽 회전을 위한 반전 알고리즘

이 기사에서는 −

Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
Output : { 43, 7, 3, 7, 4, 6, 2, 6 }
Explanation : Rotating each element of array by 4-element to the right gives { 43, 7, 3, 7, 4, 6, 2, 6 }.

Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
Output : { 4, 9, 3, 8, 5, 8, 2, 1 }

해결책을 찾는 방법

과 같이 주어진 배열을 k 요소만큼 오른쪽으로 회전하는 반전 알고리즘에 대해 알아봅니다. 각 요소를 오른쪽으로 이동하고 프로세스를 k 번 반복합니다. , 이 문제를 쉽게 해결할 수 있습니다. 하지만 시간 복잡도가 O(k * N)이므로 시간이 더 걸립니다.

반전 알고리즘: 반전은 배열을 뒤집는 것입니다. 배열 회전은 특정 요소 범위를 뒤집어 수행할 수 있습니다. 이 알고리즘에 따르면 -

• 먼저 전체 배열을 뒤집습니다.
• k가 N보다 크므로 k 모듈로 k 모듈로 N(배열 크기)을 수정합니다.
• 배열의 처음 k개 요소를 뒤집어서 순서대로 배치하세요.
• 그런 다음 나머지 요소의 범위를 반대로 바꿉니다(예: k에서 N-1로).
• li>

Example

using namespace std;
#include <bits/stdc++.h>

void reverse(int nums[], int start,int end) {
   int temp=0;
   // reversing array with swapping start element with end element.
   while(start<=end){
      temp=nums[end];
      nums[end]=nums[start];
      nums[start]=temp;
      start++;
      end--;
   }
}

int main() {
   int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 };

   int N = sizeof(arr)/sizeof(arr[0]);

   int k = 4;
   // reversing whole array
   reverse(arr, 0, N-1);
   k = k%N;
   // reversing element range of 0 to k-1.

   reverse(arr, 0, k-1);
   // reversing element range of k to last element.
   reverse(arr, k, N-1);
   cout << "Array after rotating by k-elements : ";
   for(int i = 0;i<N;i++)
      cout << arr[i] << " ";
   return 0;
}

Output

Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3

Conclusion

이번 글에서는 반전 알고리즘을 사용하여 k개 요소에 의한 배열의 오른쪽 회전 문제에 대해 논의했습니다. 이 문제를 해결하기 위해 반전 알고리즘이 무엇인지, 어떻게 구현하는지에 대해 논의했습니다. 이 문제를 해결하기 위해 C++ 코드에 대해서도 논의했습니다. 이 코드는 C, Java, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++로 작성된 배열의 오른쪽 회전을 위한 반전 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!