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 modulo k modulo N (配列サイズ) を変更します。
• 配列の最初の k 個の要素を反転して順序どおりにします。
• 次に、残りの要素の範囲を逆にします (つまり、k から N-1 まで)。
• li>

例

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;
}

出力

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

結論

この記事では、k による逆アルゴリズムの使用について説明しました。配列の要素を右回転します。反転アルゴリズムとは何か、そしてこの問題を解決するためにそれを実装する方法について説明しました。この問題を解決するための C コードについても説明しました。このコードは、C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++で書かれた配列の右回転のための反転アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。