[路飞]_leetcode-面试题 16.16-部分排序

「这是我参与2022首次更文挑战的第17天，活动详情查看：2022首次更文挑战」

[题目地址][B站地址]

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]
复制代码

提示：

• 0 <= len(array) <= 1000000

解题思路

本题可以想到最简单直接的方法拷贝原数组并排序，然后从左向右对比元素是否相同，第一个不同的位置即为 m，同理从右向左对比元素是否相同，第一个不同的位置即为 n。

最后判断 [m,n] 是否合法，如果合法，返回 [m,n]，否则返回 [-1,-1。

这样的方法可以解决问题，但是因为进行了一次排序和两次查找，以 sort 进行排序为例，排序时间复杂度 O(nlogn)，查找两个边界的时间复杂度为 O(n)，总体时间复杂度 O(n+nlogn)。有的小伙伴可能会说可以利用 计数排序 和 基数排序 将排序时间复杂度降低为 O(n)，但是提交后效率依然不高，是因为本题我们可以不对原数组排序查找两个边界下标。

我们可以首先从左往右找右边界，初始化 n = 0，记录已处理区间中的最大值，如果在后续遍历过程中找到一个值比最大值小，说明此时出现了前大后小的情况，说明该位置是需要排序的，更新 n 等于当前下标，这样一次扫描后就确定了右边界 n。 同理可以从右往左找左边界，初始化 m = len-1（len 为输入数组长度），记录已处理区间中的最小值， 如果找到一个值比最小值大，说明此时出现了前大后小的情况，说明该位置是需要排序的，则更新左边界 m 为该下标，这样一次扫描就确定了左边界 m。

如此我们通过两次遍历数组就确定了 m 和 n，最后判断 [m,n] 是否合法，如果合法，返回 [m,n]，否则返回 [-1,-1。

动画演示

代码实现

var subSort = function (array) {
  // 获取输入数组长度
  const len = array.length
  // 如果数组长度小于2，无法找到合法区间，返回 [-1,-1]
  if (len < 2) return [-1, -1]
  // 初始化右边界及最大值
  let n = 0,
    max = array[0],
    // 初始化左边界及最小值
    m = len - 1,
    min = array[len - 1]
  // 从左向右确定右边界
  for (let i = 1; i < len; i++) {
    if (array[i] >= max) max = array[i]
    else n = i
  }
  // 从右向左确定左边界
  for (let i = len - 2; i >= 0; i--) {
    if (array[i] <= min) min = array[i]
    else m = i
  }
  // 如果区间合法，返回区间，否则返回 [-1,-1]
  return m >= n ? [-1, -1] : [m, n]
}
复制代码

至此我们就完成了 leetcode-面试题 16.16-部分排序

如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻