Program JavaScript untuk subarray tak tertib terpendek Program JavaScript untuk subarray tak tertib terpendek

Pernyataan masalah memerlukan mencari subarray tak tertib terpendek dalam tatasusunan integer. Dalam erti kata lain, kita perlu menentukan subarray terkecil yang unsur-unsurnya tidak disusun dalam susunan menaik atau menurun. Masalah ini boleh diselesaikan dalam pelbagai cara, tetapi dalam artikel ini, kita akan membincangkan penyelesaian yang mudah tetapi berkesan menggunakan JavaScript.

Jadi, mula-mula kita akan mentakrifkan apa itu subarray tidak tertib dan kemudian memahami penyataan masalah secara terperinci dan kemudian menerangkan penyelesaian langkah demi langkah menggunakan contoh dan coretan kod. Selepas membaca artikel ini, anda akan mempunyai pemahaman yang jelas tentang cara menyelesaikan masalah ini dalam JavaScript. Jadi mari kita mulakan!

Apakah subarray tidak tertib?

Subarray tidak tertib ialah subarray bersebelahan bagi tatasusunan yang unsur-unsurnya tidak disusun dalam tertib menaik atau menurun. Dalam erti kata lain, unsur-unsur dalam sub-baris tidak disusun mengikut susunan yang bertambah atau berkurang.

Contohnya: [1, 2, 3, 5, 4, 6, 7] ialah subbaris tidak tertib.

Pernyataan Masalah

Memandangkan tatasusunan integer, kita perlu mencari subarray tak tertib terpendek. Dalam erti kata lain, kita perlu mencari subarray terkecil yang unsur-unsurnya tidak disusun dalam susunan menaik atau menurun.

Sebagai contoh, mari kita pertimbangkan tatasusunan berikut: const arr = [1, 2, 5, 4, 3, 6, 7]

Dalam kes ini, subarray [5, 4, 3] ialah subarray terpendek tidak tertib.

Sekarang marilah kita memahami algoritma untuk menyelesaikan masalah ini dan kemudian kita mula melaksanakan algoritma ini menggunakan JavaScript.

Algoritma subarray terpendek tak tertib

Input - susunan n integer

Output - panjang subarray terpendek tidak tertib

Langkah 1 - Permulaan permulaan = 0, tamat = n-1

LANGKAH 2 - Lintas tatasusunan dari kiri ke kanan dan cari elemen pertama yang lebih besar daripada jiran kanannya. Tetapkan indeksnya untuk bermula.

LANGKAH 3 - Lintas tatasusunan dari kanan ke kiri dan cari elemen pertama yang lebih kecil daripada jiran kirinya. Tetapkan indeksnya untuk tamat.

Langkah 4 - Cari elemen terkecil dan terbesar dalam subarray dari awal hingga akhir.

LANGKAH 5 - Ulangi tatasusunan dari 0 hingga mula-1 dan cari indeks elemen pertama yang lebih besar daripada elemen terkecil yang terdapat dalam langkah 4. Tetapkan indeksnya ke kiri.

LANGKAH 6 - Lelar melalui tatasusunan dari hujung+1 hingga n-1 dan cari indeks elemen pertama yang lebih kecil daripada elemen terbesar yang terdapat dalam langkah 4. Tetapkan indeksnya ke kanan.

Langkah 7 - Panjang subarray tak tertib terpendek ialah (kanan - kiri + 1).

Contoh

Dalam contoh di bawah, kita mula-mula mencari indeks permulaan dan penghujung subarray tidak tertib dengan mengulang tatasusunan masing-masing dari awal dan akhir. Kami kemudian mencari elemen terkecil dan terbesar dalam subarray, dan kemudian melintasi tatasusunan dari awal dan akhir masing-masing untuk mencari indeks kiri dan kanan subarray.

Akhir sekali, kami mengembalikan panjang subarray tak tertib terpendek dengan menolak indeks kanan daripada indeks kiri dan menambah 1.

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.

Kesimpulan

Kami membincangkan setiap nuansa tentang cara melaksanakan masalah subarray tidak tertib terpendek menggunakan JavaScript. Kami berharap dengan artikel ini, orang ramai boleh mencari dan membetulkan isu yang berkaitan dengan subarray tidak tertib dalam kod mereka dengan mudah.

Atas ialah kandungan terperinci Program JavaScript untuk subarray tak tertib terpendek Program JavaScript untuk subarray tak tertib terpendek. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!