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.