Rumah > pembangunan bahagian belakang > C++ > Algoritma penyongsangan untuk putaran kanan tatasusunan yang ditulis dalam C++

Algoritma penyongsangan untuk putaran kanan tatasusunan yang ditulis dalam C++

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Lepaskan: 2023-09-08 20:17:02
ke hadapan
1179 orang telah melayarinya

Algoritma penyongsangan untuk putaran kanan tatasusunan yang ditulis dalam C++

Dalam artikel ini kita akan belajar tentang algoritma pembalikan untuk memutar tatasusunan yang diberikan ke kanan dengan elemen k seperti −

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 }
Salin selepas log masuk

Cara mencari penyelesaian

dengan mengalihkan setiap elemen ke kanan dan mengulangi proses k kali , anda boleh menyelesaikan masalah ini dengan mudah. Tetapi ini akan mengambil lebih banyak masa kerana kerumitan masanya ialah O(k * N).

Algoritma Penyongsangan: Penyongsangan ialah pembalikan tatasusunan, memutar tatasusunan boleh dilakukan dengan membalikkan julat elemen tertentu. Mengikut algoritma ini -

  • Pertama, terbalikkan keseluruhan tatasusunan.
  • Ubah suai k modulo k modulo N (saiz tatasusunan), kerana k lebih besar daripada N.
  • Terbalikkan elemen k pertama tatasusunan untuk menyusunnya.
  • Kemudian terbalikkan julat elemen yang tinggal, iaitu dari k ke N-1.
  • li>

Contoh

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;
}
Salin selepas log masuk

Output

Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
Salin selepas log masuk

Kesimpulan

Dalam artikel ini, kita membincangkan masalah putaran betul tatasusunan dengan elemen k menggunakan algoritma penyongsangan. Kami membincangkan apakah algoritma penyongsangan dan cara melaksanakannya untuk menyelesaikan masalah ini. Kami juga membincangkan kod C++ untuk menyelesaikan masalah ini. Kita boleh menulis kod ini dalam mana-mana bahasa lain seperti C, Java, Python, dll. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Algoritma penyongsangan untuk putaran kanan tatasusunan yang ditulis dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan