Das JavaScript-Programm prüft, ob das Array durch Drehen vergrößert oder verkleinert werden kann

Die Drehung eines Arrays bedeutet, dass davon ausgegangen wird, dass das Array ein kreisförmiges Array ist. Bei jeder Drehung werden die Elemente des Arrays um einen Index nach links oder rechts gedreht, und die Elemente an einem Ende können den Wert des anderen Endes annehmen . Eine zunehmende Anordnung bedeutet, dass jedes Element größer oder gleich dem vorherigen Element ist. Eine abnehmende Anordnung bedeutet, dass jedes Element kleiner oder gleich dem vorherigen Element ist.

In diesem Problem erhalten wir ein Array und können das Array nach links oder rechts drehen und müssen herausfinden, ob wir das Array nach einer bestimmten Drehung (die Null sein kann) vergrößern oder verkleinern können. p>

Naive Methode

Bei dieser Methode drehen wir das Array und prüfen bei jeder Drehung, ob das aktuelle Array zunimmt oder abnimmt.

Beispiel

Im folgenden Beispiel prüfen wir, ob das angegebene Array durch Drehen vergrößert oder verkleinert werden kann. Nachfolgend finden Sie die Eingabe und die erwartete Ausgabe.

Eingabe: arr = [3, 4, 5, 6, 1, 2]

Erwartete Ausgabe: Ja

Eingabe: arr = [5, 1, 6, 2, 5, 3]

Erwartete Ausgabe: Nein

Beispiel

// function to rotate the given array
function rotate(arr){
   var l = 0;
   var r = arr.length-1;
   while(l < r){
      arr[l] += arr[r];
      arr[r] = arr[l]-arr[r];
      arr[l] = arr[l]-arr[r];
      l++;
   }
   return arr;
}

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return true;
}

// function to check if the given array is decreasing or not
function decreasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   for(var i = 1; i < len; i++){
      if(arr[i] > arr[i-1]){
         return false;
      }
   }
   return true;
}

// function to check whether the given array can become
// increasing or decreasing after certain rotations
function check(arr){
   var k = arr.length
   while(k--){
      if(increasing(arr) || decreasing(arr)){
         return true;
      }
      arr = rotate(arr);
   }
   return false;
}

// defining the arr's
var arr1 = [3, 4, 5, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

Ausgabe

The given array is: 
[ 3, 4, 5, 6, 1, 2 ]
Yes, after some rotations given array can be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

Die zeitliche Komplexität des obigen Codes beträgt O(N*N) und die räumliche Komplexität beträgt O(1).

Effiziente Methode

Im vorherigen Array haben wir überprüft, ob sich das Array mit jeder Drehung vergrößert oder verkleinert. Bei dieser Methode überprüfen wir teilweise das vergrößerte oder verkleinerte Array.

Beispiel

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   var i = 0;
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         break;
      }
   }
   if(i == len) return true;
   i++;
   for(; i< len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return arr[len-1] <= arr[0];
}

// function to check if the given array is decreasing or not
function decreasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   var i = 0;
   for(var i = 1; i < len; i++){
      if(arr[i] > arr[i-1]){
         break;
      }
   }
   if(i == len) return true;
   i++;
   for(; i< len; i++){
      if(arr[i] > arr[i-1]){
         return false;
      }
   }
   return arr[len-1] >= arr[0];
}

// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
   if(increasing(arr) || decreasing(arr)){
      return true;
   }
   else{
      return false;
   }
}

// defining the arr's
var arr1 = [3, 4, 7, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

Ausgabe

The given array is: 
[ 3, 4, 7, 6, 1, 2 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

Die zeitliche Komplexität des obigen Codes beträgt O(N) und die räumliche Komplexität beträgt O(1).

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, das prüft, ob ein bestimmtes Array durch Drehen vergrößert oder verkleinert werden kann. Wir haben zwei Methoden mit der Zeitkomplexität O(N*N) und O(N) und der Raumkomplexität O(1) implementiert.

Das obige ist der detaillierte Inhalt vonDas JavaScript-Programm prüft, ob das Array durch Drehen vergrößert oder verkleinert werden kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!