最小长度未排序连续子数组
Minimum length Unsorted Continous subarray
我正在尝试这个常见的面试问题最短未排序连续子数组问题陈述如下所示。
Given an unsorted array A of size N. Find the subarray 0 <= s < r < N such that sorting this subarray makes the whole array sorted.
我的方法：
我的想法是基于选择排序。我们可以遍历给定的数组 A 选择元素 A[i]。对于选择的每个这样的元素，我试图确定它在排序数组中的正确位置。为此，我将 A[i] 与每个 A[j] 进行了比较，因此 i < j < N。但是正如您所看到的，这种方法花费了 O(N*N) 时间复杂度，但法官期望的解决方案具有 O(N) 时间复杂度，并且显然 O(1) 额外 space。谁能帮我提供一个可接受的解决方案？
步骤：
1）从左起第一个索引和右起第一个索引，其中排序的条件
数组失败，即 A[i] > A[i+1]
2）然后找到这个范围内的最小和最大元素
3）如果得到的最小元素不大于前面的所有元素
然后考虑范围，更新起始索引
4）如果得到的最大元素不小于后面的所有元素
然后考虑范围，更新结束索引
5) 这样得到的起始索引和结束索引会给我们正确的答案
此方法的时间复杂度为 O(n)，space 复杂度为 O(1)
如果还有疑问，可以参考这个视频。
Link : https://youtu.be/UfBfr-VRYOU
我正在尝试这个常见的面试问题最短未排序连续子数组问题陈述如下所示。
Given an unsorted array
Aof sizeN. Find the subarray0 <= s < r < Nsuch that sorting this subarray makes the whole array sorted.
我的方法：
我的想法是基于选择排序。我们可以遍历给定的数组 A 选择元素 A[i]。对于选择的每个这样的元素，我试图确定它在排序数组中的正确位置。为此，我将 A[i] 与每个 A[j] 进行了比较，因此 i < j < N。但是正如您所看到的，这种方法花费了 O(N*N) 时间复杂度，但法官期望的解决方案具有 O(N) 时间复杂度，并且显然 O(1) 额外 space。谁能帮我提供一个可接受的解决方案？
步骤：
1）从左起第一个索引和右起第一个索引，其中排序的条件
数组失败，即 A[i] > A[i+1]
2）然后找到这个范围内的最小和最大元素
3）如果得到的最小元素不大于前面的所有元素
然后考虑范围，更新起始索引
4）如果得到的最大元素不小于后面的所有元素
然后考虑范围，更新结束索引
5) 这样得到的起始索引和结束索引会给我们正确的答案
此方法的时间复杂度为 O(n)，space 复杂度为 O(1)
如果还有疑问，可以参考这个视频。
Link : https://youtu.be/UfBfr-VRYOU