JavaScript最短無序子陣列程式JavaScript最短無序子陣列程式

---

題目要求在一個整數陣列中找到最短的無序子陣列。換句話說，我們需要找到元素不是按升序或降序排列的最小子陣列。這個問題可以透過多種方法解決，但在本文中，我們將討論一種使用JavaScript的簡單高效的解決方案。

所以，我們首先定義什麼是無序子陣列，然後詳細瞭解問題陳述，然後逐步解釋使用示例和程式碼片段的解決方案。在本文結束時，您將清楚地瞭解如何在JavaScript中解決這個問題。讓我們開始吧！

什麼是無序子陣列？

無序子陣列是陣列的一個連續子陣列，其中元素不是按升序或降序排列的。換句話說，子陣列中的元素並非以遞增或遞減的順序排列。

例如：[1, 2, 3, 5, 4, 6, 7] 是一個無序子陣列。

問題陳述

給定一個整數陣列，我們需要找到最短的無序子陣列。換句話說，我們需要找到元素不是按升序或降序排列的最小子陣列。

例如，讓我們考慮以下陣列：const arr = [1, 2, 5, 4, 3, 6, 7]

在這種情況下，子陣列 [5, 4, 3] 是最短的無序子陣列。

現在讓我們瞭解解決這個問題的演算法，然後我們轉向使用JavaScript實現該演算法。

最短無序子陣列演算法

輸入 − 一個包含n個整數的陣列

輸出 − 最短無序子陣列的長度

步驟1 − 初始化 start = 0, end = n-1

步驟2 − 從左到右遍歷陣列，找到第一個大於其右邊鄰居的元素。將其索引設定為start。

步驟3 − 從右到左遍歷陣列，找到第一個小於其左邊鄰居的元素。將其索引設定為end。

步驟4 − 找到從start到end的子陣列中的最小和最大元素。

步驟5 − 從0到start-1遍歷陣列，找到第一個大於步驟4中找到的最小元素的元素的索引。將其索引設定為left。

步驟6 − 從end+1到n-1遍歷陣列，找到第一個小於步驟4中找到的最大元素的元素的索引。將其索引設定為right。

步驟7 − 最短無序子陣列的長度是 (right - left + 1)。

示例

在下面的示例中，我們首先透過分別從開頭和結尾迭代陣列來找到無序子陣列的起始和結束索引。然後，我們找到子陣列中的最小和最大元素，然後我們透過分別從開頭和結尾迭代陣列來找到子陣列的左和右索引。

最後，我們透過從左索引中減去右索引並加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.

結論

我們討論瞭如何使用JavaScript執行最短無序子陣列問題的每一個細微之處。我們希望透過這篇文章，可以輕鬆找到並修復程式碼中與無序子陣列相關的錯誤。