JavaScript-Programm: Überprüfen Sie, ob das Array sortiert ist, und drehen Sie es

Ein sortiertes Array ist ein Array, in dem alle Elemente in aufsteigender Reihenfolge angeordnet sind. Wir erhalten ein Array der Größe N und ein Array mit unterschiedlichen Ganzzahlen (was bedeutet, dass jede Ganzzahl nur einmal vorkommt). Wir müssen prüfen, ob das Array sortiert und im Uhrzeigersinn gedreht ist. Wenn das Array hier sortiert und gedreht wird, müssen wir „JA“ zurückgeben, andernfalls müssen wir „NEIN“ zurückgeben.

Hinweis – Hier geht es um Sortierung und Rotation, was bedeutet, dass es mindestens eine Rotation geben sollte. Wir können ein sortiertes Array nicht als sortiertes und gedrehtes Array behandeln.

Angenommen, wir haben ein Array der Größe N erhalten

Eintreten

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

Ausgabe

Yes, the given array is sorted and rotated. 

Anleitung

Array ist ein sortiertes Array und wird um 1 Bit gedreht

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

Das um 1 Position sortierte und gedrehte Array stimmt mit dem Eingabearray überein, sodass die Ausgabe „Ja“ lautet.

Eintreten

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

Ausgabe

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

Anleitung

Das angegebene Array ist ein unsortiertes und gedrehtes Array

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]

Weder die sortierten noch gedrehten Arrays oben stimmen mit dem Eingabearray überein, daher lautet die Antwort: Nein.

Methode

Hier besprechen wir zwei Methoden. Sehen wir sie uns in den folgenden Abschnitten an -

Methode 1: Überprüfen Sie, ob das Array sortiert und gedreht ist, indem Sie das Pivot-Element (Mindestanzahl) finden

Die Idee dieser Methode ist, dass wir die Mindestanzahl finden und wenn unser Array sortiert und gedreht wird, sollten die Werte vor und nach der Mindestanzahl sortiert sein.

Beispiel

// 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")
}

Zeitkomplexität – O(N), wobei N die Größe des Arrays ist.

Raumkomplexität – O(1), da wir keinen zusätzlichen Raum nutzen.

Methode 2: Überprüfen Sie, ob das Array sortiert und gedreht ist, indem Sie benachbarte Inversionen berechnen

Die Idee dieser Methode besteht darin, dass wir das Array durchlaufen und prüfen, ob das vorherige Element kleiner als das aktuelle Element ist. Bei einem sortierten und gedrehten Array muss die Anzahl 1 sein, wenn das vorherige Element größer als das aktuelle Element ist, andernfalls wird das Array nicht sortiert und gedreht.

Beispiel

// 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")
}

Zeitkomplexität – O(N), wobei N die Größe des Arrays ist.

Raumkomplexität – O(1), da wir keinen zusätzlichen Raum nutzen.

Fazit

In diesem Tutorial haben wir besprochen, wie man überprüft, ob ein Array sortiert und gedreht ist. Hier sehen wir zwei Methoden: Die erste besteht darin, den Pivot (also das kleinste Element) zu finden, und die andere darin, benachbarte Inversionen zu berechnen. Die zeitliche und räumliche Komplexität beider Methoden ist gleich, d. h. O(N) bzw. O(1).

Das obige ist der detaillierte Inhalt vonJavaScript-Programm: Überprüfen Sie, ob das Array sortiert ist, und drehen Sie es. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!