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
N = 5 Array = [5, 1, 2, 3, 4]
Yes, the given array is sorted and rotated.
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.
N = 6 Array = [6, 5, 1, 2, 3, 4]
No, the given array is not sorted and rotated array.
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.
Hier besprechen wir zwei Methoden. Sehen wir sie uns in den folgenden Abschnitten an -
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.
// 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.
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.
// 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.
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!
window.prompt
Was tun, wenn die Win8wifi-Verbindung nicht verfügbar ist?
So stellen Sie eine MySQL-Datenbank wieder her
So beheben Sie das Problem „Zugriff verweigert'.
So extrahieren Sie Audio aus Video in Java
Lösung für den schwarzen Bildschirm beim Start von Ubuntu
Welche Karte ist eine TF-Karte?
So ändern Sie phpmyadmin auf Chinesisch
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
