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执行最短无序子数组问题的每一个细微之处。我们希望通过这篇文章，可以轻松找到并修复代码中与无序子数组相关的错误。