JavaScript-Programm für das kürzeste ungeordnete Subarray. JavaScript-Programm für das kürzeste ungeordnete Subarray

Die Problemstellung erfordert das Finden des kürzesten ungeordneten Unterarrays in einem Array von ganzen Zahlen. Mit anderen Worten: Wir müssen das kleinste Subarray bestimmen, dessen Elemente nicht in aufsteigender oder absteigender Reihenfolge sortiert sind. Dieses Problem kann auf viele Arten gelöst werden. In diesem Artikel besprechen wir jedoch eine einfache, aber effektive Lösung mithilfe von JavaScript.

Also definieren wir zunächst, was ein ungeordnetes Subarray ist, verstehen dann die Problemstellung im Detail und erklären dann Schritt für Schritt die Lösung anhand von Beispielen und Codeausschnitten. Nachdem Sie diesen Artikel gelesen haben, wissen Sie genau, wie Sie dieses Problem in JavaScript lösen können. Also fangen wir an!

Was ist ein ungeordnetes Subarray?

Ein ungeordnetes Subarray ist ein zusammenhängendes Subarray eines Arrays, bei dem die Elemente nicht in aufsteigender oder absteigender Reihenfolge angeordnet sind. Mit anderen Worten: Die Elemente im Subarray sind nicht in aufsteigender oder absteigender Reihenfolge angeordnet.

Zum Beispiel: [1, 2, 3, 5, 4, 6, 7] ist ein ungeordnetes Subarray.

Problemstellung

Angesichts eines Arrays von ganzen Zahlen müssen wir das kürzeste ungeordnete Subarray finden. Mit anderen Worten: Wir müssen das kleinste Subarray finden, dessen Elemente nicht in aufsteigender oder absteigender Reihenfolge sortiert sind.

Betrachten wir zum Beispiel das folgende Array: const arr = [1, 2, 5, 4, 3, 6, 7]

In diesem Fall ist das Subarray [5, 4, 3] das kürzeste ungeordnete Subarray.

Lassen Sie uns nun den Algorithmus zur Lösung dieses Problems verstehen und dann beginnen wir mit der Implementierung dieses Algorithmus mithilfe von JavaScript.

Kürzester ungeordneter Subarray-Algorithmus

Eingabe – Array von n Ganzzahlen

Ausgabe – Länge des ungeordneten kürzesten Subarrays

Schritt 1 – Initialisierungsstart = 0, Ende = n-1

SCHRITT 2 – Durchlaufen Sie das Array von links nach rechts und finden Sie das erste Element, das größer als sein rechter Nachbar ist. Legen Sie den Index auf Start fest.

SCHRITT 3 – Durchlaufen Sie das Array von rechts nach links und finden Sie das erste Element, das kleiner als sein linker Nachbar ist. Setzen Sie den Index auf Ende.

Schritt 4 – Finden Sie das kleinste und größte Element im Subarray von Anfang bis Ende.

SCHRITT 5 – Durchlaufen Sie das Array von 0 bis start-1 und finden Sie den Index des ersten Elements, das größer als das kleinste in Schritt 4 gefundene Element ist. Setzen Sie den Index nach links.

SCHRITT 6 – Durchlaufen Sie das Array von Ende+1 bis n-1 und finden Sie den Index des ersten Elements, das kleiner als das größte in Schritt 4 gefundene Element ist. Setzen Sie den Index nach rechts.

Schritt 7 – Die Länge des kürzesten ungeordneten Subarrays beträgt (rechts – links + 1).

Beispiel

Im folgenden Beispiel ermitteln wir zunächst den Start- und Endindex des ungeordneten Unterarrays, indem wir das Array vom Anfang bzw. Ende aus iterieren. Wir finden dann die kleinsten und größten Elemente im Subarray und durchlaufen dann das Array vom Anfang bzw. Ende, um den linken und rechten Index des Subarrays zu finden.

Schließlich geben wir die Länge des kürzesten ungeordneten Subarrays zurück, indem wir den rechten Index vom linken Index subtrahieren und 1 addieren.

function shortestUnorderedSubarray(arr) {
   let n = arr.length;
   let start = 0, end = n - 1;
   // find start index
   for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
         start = i;
         break;
      }
   }
   // find end index
   for (let i = n - 1; i > 0; i--) {
      if (arr[i] < arr[i - 1]) {
         end = i;
         break;
      }
   }
   // find min and max element in subarray
   let min = arr[start], max = arr[start];
   for (let i = start + 1; i <= end; i++) {
      if (arr[i] < min) {
         min = arr[i];
      }
      if (arr[i] > max) {
         max = arr[i];
      }
   }
   // find left index
   let left = 0;
   for (let i = 0; i <= start; i++) {
      if (arr[i] > min) {
         left = i;
         break;
      }
   }
   // find right index
   let right = n - 1;
   for (let i = n - 1; i >= end; i--) {
      if (arr[i] < max) {
         right = i;
         break;
      }
   }
   // return length of shortest un-ordered subarray
   return right - left + 1;
}
// Example usage:
const arr = [1, 2, 5, 4, 3, 6, 7]
console.log("Array:", JSON.stringify(arr))
const len = shortestUnorderedSubarray(arr)
console.log("The length shortest un-ordered subarray: ", len);
// Output: 3, as [5, 4, 3] is the shortest un-ordered subarray with length 3.

Fazit

Wir haben jede Nuance besprochen, wie man das kürzeste ungeordnete Subarray-Problem mit JavaScript lösen kann. Wir hoffen, dass Benutzer mit diesem Artikel Probleme im Zusammenhang mit ungeordneten Subarrays in ihrem Code leicht finden und beheben können.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm für das kürzeste ungeordnete Subarray. JavaScript-Programm für das kürzeste ungeordnete Subarray. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!