最短无序子数组的 JavaScript 程序最短无序子数组的 JavaScript 程序

WBOY 转载: 2023-09-01 16:13:07 814浏览

问题陈述要求在整数数组中找到最短的无序子数组。换句话说，我们需要确定元素不按升序或降序排序的最小子数组。这个问题可以通过多种方法来解决，但在本文中，我们将讨论使用 JavaScript 的简单而有效的解决方案。

因此，首先我们将首先定义什么是无序子数组，然后详细理解问题陈述，然后继续使用示例和代码片段解释逐步解决方案。读完本文后，您将清楚地了解如何在 JavaScript 中解决这个问题。那么让我们开始吧！

什么是无序子数组？

无序子数组是数组的连续子数组，其中元素不按升序或降序排列。换句话说，子数组中的元素不是按照递增或递减的顺序排列的。

例如：[1, 2, 3, 5, 4, 6, 7] 是一个无序子数组。

问题陈述

给定一个整数数组，我们需要找到最短的无序子数组。换句话说，我们需要找出元素不按升序或降序排序的最小子数组。

例如，让我们考虑以下数组：const arr = [1, 2, 5, 4, 3, 6, 7]

在这种情况下，子数组 [5, 4, 3] 是最短的无序子数组。

现在让我们了解解决这个问题的算法，然后我们开始使用 JavaScript 实现这个算法。

最短无序子数组算法

输入 - n 个整数的数组

输出 - 无序的最短子数组的长度

第 1 步 - 初始化开始 = 0，结束 = n-1

STEP 2 - 从左到右遍历数组并找到第一个大于其右邻居的元素。将其索引设置为开始。

STEP 3 - 从右向左遍历数组并找到第一个小于其左邻居的元素。将其索引设置为结束。

第 4 步 - 从开始到结束查找子数组中的最小和最大元素。

STEP 5 - 从 0 到 start-1 遍历数组，找到第一个大于步骤 4 中找到的最小元素的元素的索引。将其索引设置为左侧。

STEP 6 - 从 end+1 到 n-1 遍历数组，找到第一个小于步骤 4 中找到的最大元素的元素的索引。将其索引设置为右侧.

第 7 步 - 最短无序子数组的长度为（右 - 左 + 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.