Program JavaScript: semak sama ada tatasusunan diisih dan putarkannya

Tatasusunan tersusun ialah tatasusunan di mana semua elemen disusun dalam tertib menaik. Kami diberikan tatasusunan saiz N dan tatasusunan yang mengandungi integer yang berbeza (bermaksud setiap integer muncul sekali sahaja). Kita perlu menyemak sama ada tatasusunan diisih dan diputar mengikut arah jam. Di sini, jika tatasusunan diisih dan diputar, kita mesti mengembalikan "YA", jika tidak, kita mesti mengembalikan "TIDAK".

Nota - Di sini kita bercakap tentang penyisihan dan putaran bermakna sekurang-kurangnya perlu ada satu putaran. Kami tidak boleh merawat tatasusunan yang diisih sebagai tatasusunan yang diisih dan diputar.

Andaikan kita telah diberikan array saiz N

Masuk

N = 5
Array = [5, 1, 2, 3, 4]

Output

Yes, the given array is sorted and rotated. 

Arahan

Array diisih tatasusunan dan diputar sebanyak 1 bit

Sorted array = [1, 2, 3, 4, 5]
Rotated above sorted array by 1 place, we get = [5, 1, 2, 3, 4]

Tatasusunan yang diisih mengikut 1 kedudukan dan diputar sepadan dengan tatasusunan input, jadi outputnya ialah "ya".

Masuk

N = 6
Array = [6, 5, 1, 2, 3, 4]

Output

No, the given array is not sorted and rotated array. 

Arahan

Tatasusunan yang diberikan ialah tatasusunan yang tidak diisih dan diputar

Sorted array = [1, 2, 3, 4, 5, 6]
Rotated above sorted array by 1 place, we get = [6, 1, 2, 3, 4, 5]
Rotated above sorted array by 2 place, we get = [5, 6, 1, 2, 3, 4]
Rotated above sorted array by 3 place, we get = [4, 5, 6, 1, 2, 3]
Rotated above sorted array by 4 place, we get = [3, 4, 5, 6, 1, 2]
Rotated above sorted array by 5 place, we get = [2, 3, 4, 5, 6, 1]

Tiada tatasusunan yang diisih atau diputar di atas tidak sepadan dengan tatasusunan input, jadi jawapannya, tidak.

Kaedah

Di sini kita akan membincangkan dua kaedah. Mari lihat mereka dalam bahagian di bawah -

Kaedah 1: Semak sama ada tatasusunan diisih dan diputar dengan mencari elemen pangsi (nombor minimum)

Idea kaedah ini ialah kita akan mencari nombor minimum dan jika tatasusunan kita diisih dan diputar, nilai sebelum dan selepas nombor minimum hendaklah mengikut cara yang disusun.

Contoh

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var mi = Number.MAX_VALUE; // variable to find the smallest number 
   var idx_min = -1; // variable to store the index of smallest number;
   
   // traversing over the array to find the minimum element and its index
   for(var i = 0; i < len; i++){
      if (arr[i] < mi){
         mi = arr[i];
         idx_min = i;
      }
   }
   
   // traversing over the array to find that all the elements 
   // before the minimum element are sorted 
   for(var i = 1; i < idx_min; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }
   
   // traversing over the array to find that all the elements after the minimum element are sorted 
   for(var i = idx_min + 1; i < len; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }
   
   // checking if the last element of the array is smaller than the first element or not 
   if(arr[len-1] > arr[0]){
      return false;
   }
   else{
      return true;
   }
}

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

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}

Kerumitan masa - O(N), dengan N ialah saiz tatasusunan.

Kerumitan Ruang - O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Kaedah 2: Semak sama ada tatasusunan diisih dan diputar dengan mengira penyongsangan bersebelahan

Idea kaedah ini ialah kita akan mengulangi tatasusunan dan menyemak sama ada elemen sebelumnya kurang daripada elemen semasa. Untuk tatasusunan yang diisih dan diputar, kiraan mestilah 1 jika elemen sebelumnya lebih besar daripada elemen semasa, jika tidak tatasusunan tidak diisih dan diputar.

Contoh

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var count = 0; // variable to count the adjacent inversions
   
   // traversing over the array to find the number of times first element is smaller than second 
   for(var i = 1; i < len; i++){
      if (arr[i] < arr[i-1]){
         count++;
      }
   }
   
   // checking if the last element of the array is smaller 
   // than the first element or not and inversion must be equal to 1
   if(arr[len-1] > arr[0] || count != 1){
      return false;
   }
   else{
      return true;
   }
}

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

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}

Kerumitan masa - O(N), dengan N ialah saiz tatasusunan.

Kerumitan Ruang - O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Kesimpulan

Dalam tutorial ini, kami membincangkan cara menyemak sama ada tatasusunan diisih dan diputar. Di sini kita melihat dua kaedah, yang pertama ialah mencari pangsi (yang bermaksud elemen terkecil) dan yang lain adalah dengan mengira penyongsangan bersebelahan. Kerumitan masa dan ruang bagi kedua-dua kaedah adalah sama, iaitu O(N) dan O(1) masing-masing.

Atas ialah kandungan terperinci Program JavaScript: semak sama ada tatasusunan diisih dan putarkannya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!