algorithm - 最小排序子数组

Question

这是一道面试题。给定一个整数数组，编写一个方法来查找索引 m 和 n，这样如果你对元素 m 到 n 进行排序，整个数组都会被排序。最小化纳米。即找到最小的序列。

Answer 1

观察

m 之前的整数应该是升序的并且小于（或等于）之后的任何整数。

算法

1. 从第一个元素开始，并在第一个减少时停止。（子阵列 SA）

2. 之后找到最小值。(分钟)

3. 起点就在 SA 中小于（或等于）MIN 的最大整数之后。（找到m）

复杂

上）

---

对 n 做类似的事情。

Answer 2

您需要跟踪四件事：

1. 在开始的排序区域结束
2. 排序区域的开始在末尾
3. 开始区域后的最小数量
4. 结束区域前的最大数量

首先找出 1 和 2 的初步值，从头到尾扫描数组，直到找到放错位置的值。

然后，您在初步 1 之后扫描所有内容，以找到最小数量。这是你的 3。用同样的方法找到 4。

现在你回溯到数组的起始区域，直到找到最小值应该在的位置。这是 1 的确切答案，也是您的m.

以相同的方式通过回溯结束区域来找到n最大数量应该在哪里。