Program JavaScript untuk algoritma pertukaran blok untuk putaran tatasusunan

Putaran elemen tatasusunan bermaksud menggerakkan elemen tatasusunan yang diberikan ke kiri atau kanan mengikut bilangan kedudukan tertentu. Kami menganggap bahawa tatasusunan adalah dalam bentuk gelung dan putar elemen tepi ke hujung yang lain. Algoritma pertukaran blok untuk putaran tatasusunan bermaksud memutarkan elemen tatasusunan dengan jumlah tertentu, tetapi bukannya menggunakan putaran, teknik pertukaran digunakan. Kami akan melaksanakan kaedah rekursif dan berulang.

Masuk

The given array is [ 1, 2, 3, 4, 5, 6, 7].
The number of rotations by which we have to rotate is 3. 

Output

[4, 5, 6, 7, 1, 2, 3]

Arahan

Kami boleh menggunakan algoritma pertukaran dan mendapatkan hasilnya, kami akan melaksanakannya dalam bahagian seterusnya.

Kaedah rekursif

Dalam kaedah ini, kami akan cuba menganggap bahawa kami mempunyai dua tatasusunan, yang pertama mempunyai saiz bilangan putaran yang diberikan dan satu lagi mempunyai saiz jumlah saiz tolak bilangan elemen yang diberikan.

Jika saiz tatasusunan pertama adalah kecil maka kita akan menukar elemen tatasusunan pertama dan elemen terakhir adalah sama dengan saiz tatasusunan pertama, jika saiz tatasusunan pertama lebih besar daripada kita akan menukar elemen tatasusunan tatasusunan pertama sama dengan Saiz tatasusunan kedua tatasusunan yang diberikan.

Untuk elemen yang selebihnya, kami akan memanggil fungsi rekursif dengan menukar tatasusunan swap.

Contoh

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }
   
   // special case when the number of elements to rotate 
   // is half of the size of the given array
   if(n == 2*k){
      arr = swap(arr, 0, n - k, k);
      return;
   }		
   
   // if the first part is short	
   if(2*k < n) {
      arr = swap(arr, 0, n - k, k);
      rotate(arr, k, n - k);	
   }
   else{	
   
      // if second part is short
      arr = swap(arr, 0, k, n - k);
      rotate(arr + n - k, 2 * k - n, k);
   }
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

//Defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah N, dengan N ialah saiz tatasusunan yang diberikan.

Kod di atas mempunyai kerumitan ruang N, tetapi itu hanya jika kita menganggap memori yang diduduki oleh timbunan rekursif.

Kaedah berulang

Kaedah lelaran adalah sama dengan kaedah rekursif, cuma bezanya kami bekerja dalam gelung sementara dan bukannya menggunakan panggilan rekursif. Mari lihat kodnya.

Contoh

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }
   var i = k;
   var j = n - k;
   while (i != j){
      if(i < j){
      
         // if the first array is shorter 
         arr = swap(arr, k - i, k + j - i, i);
         j -= i;
      }
      else{ 
      
         // if the second array is shorter 
         arr = swap(arr, k - i, k, j);
         i -= j;
      }
   }
   arr = swap(arr, k - i, k, i);
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

// defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah N, dengan N ialah saiz tatasusunan yang diberikan.

Kerumitan ruang kod di atas ialah 1 atau tetap kerana kami tidak menggunakan sebarang ruang tambahan di sini.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program JavaScript untuk memutar tatasusunan dengan bilangan putaran tertentu dengan menggunakan algoritma pertukaran blok. Kami melaksanakan algoritma pertukaran blok menggunakan pendekatan berulang dengan masa O(N) dan kerumitan ruang O(1), sambil menggunakan pendekatan rekursif dengan kerumitan ruang O(N).

Atas ialah kandungan terperinci Program JavaScript untuk algoritma pertukaran blok untuk putaran tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!