部分排序 （面试题 16）
本文内容为算法训练营一期内容，仅限训练营学员观看。
一、题目描述
给定一个整数数组，编写一个函数，找出索引 m 和 n ，只要将索引区间 [m,n] 的元素排好序，整个数组就是有序的。（默认是递增有序数组）
注意：n – m 尽量最小，也就是说，找出符合条件的最短序列。
函数返回值为 [m,n] ，若不存在这样的 m 和 n（例如整个数组是有序的），请返回 [-1,-1] 。
二、题目解析
对于元素 a[i] 来说，如果它左边存在大于 a[i] 的元素，那么 a[i] 是一定要加入到被排序的序列内。
如果它右边存在小于 a[i] 的元素，那么a[i]` 也要加入到被排序的序列内。
所以，我们的目的很明确。
1、寻找最靠右的那个数，即它的左边存在大于它的数
2、寻找最靠左的那个数，即它的右边存在小于它的数
这两个数之间就是要排序的区间。
最靠右的数具备以下特征：
1、它的左边存在大于它的数
2、它的右边数都比它更大
3、相对于多个符合 1、2 要求的数，它是最靠右的
同样的，最靠左的数具备以下特征：
1、它的右边存在小于它的数
2、它的左边数都比它更小
3、相对于多个符合 1、2 要求的数，它是最靠左的
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 部分排序 （面试题 16）:https://leetcode-cn.com/problems/sub-sort-lcci/
class Solution {
public int[] subSort(int[] array) {
// 如果数组为空、或者数组没有元素、或者数组只有一个元素，找不出符合要求的序列，根据题目要求返回 [-1,-1]
if(array == null || array.length == 0 || array.length == 1) return new int[]{-1,-1};
// 正常来说，整个数组是递增有序的，比如 1 3 5 9 10 这种
// 如果某个元素的左边存在比它更大的元素，比如 1 10 5
// 5 这个元素的左边存在 10 这个元素比它更大，一定 5 要参与到排序里去的
// 如果某个元素的右边存在比它更小的元素，比如 1 10 5
// 10 这个元素的右边存在 5 这个元素比它更小，所以 10 一定要参与到排序里去的
// 所以我们只需要寻找最靠右的那个数（满足左边存在大于它的数）
// 和最靠左的那个数（满足右边存在小于它的数）
// 那么这两个数之间就是要排序的区间了
// 第一次遍历是从尾到头进行遍历，目的是为了找出最靠左的那个数，即满足右边存在小于它的数
// 一开始默认最右边的数为最小值
int min = array[array.length - 1];
// 默认找不到的情况下 m 为 -1
int m = -1;
// 从尾到头进行遍历，直到遍历到数组的开始位置
for( int j = array.length - 2 ; j >= 0 ; j-- ){
// 获取当前遍历的元素值
int cur = array[j] ;
// 如果此时当前的元素值小于等于最小值，需要更新最小值
if(cur <= min){
// 更新最小值
min = cur;
}else{
// 如果当前元素大于了最小值，由于我们是从尾到头进行遍历，说明当前元素的右边存在小于它的数，这个元素需要加入到排序的区间
// 比如 10 9 7
// 最小值是 7 ，而 9 大于 7，所以 9 需要加入到排序的区间
// 因此更新 m 的值为 j，说明此时遍历的那些元素中 j 是最靠左的那个数
m = j;
}
}
// 第二次遍历是从尾到头进行遍历，目的是为了找出最靠右的那个数，即满足左边存在大于它的数
// 一开始默认最左边的数为最大值
int max = array[0];
// 默认找不到的情况下 n 为 -1
int n = -1;
// 从头进行遍历，直到遍历到数组的结束位置
for( int i = 1 ; i < array.length ; i++ ){
// 获取当前遍历的元素值
int cur = array[i] ;
// 如果此时当前的元素值大于等于最大值，需要更新最大值
if(cur >= max){
// 更新最大值
max = array[i];
}else{
// 如果当前元素小于了最大值，由于我们是从头到尾进行遍历，说明当前元素的左边存在大于它的数，这个元素需要加入到排序的区间
// 比如 10 9 7
// 最小值是 10 ，而 7 小于 10，所以 7 需要加入到排序的区间
// 因此更新 n 的值为 i，说明此时遍历的那些元素中 i 是最靠右的那个数
n = i;
}
}
// m 和 n 这两个数之间就是要排序的区间，返回即可
return new int[]{m,n};
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 部分排序 （面试题 16）:https://leetcode-cn.com/problems/sub-sort-lcci/
class Solution {
public:
vector<int> subSort(vector<int>& array) {
// 如果数组为空、或者数组没有元素、或者数组只有一个元素，找不出符合要求的序列，根据题目要求返回 [-1,-1]
if(array.size()==0 || array.size()==1){
return {-1,-1};
}
// 正常来说，整个数组是递增有序的，比如 1 3 5 9 10 这种
// 如果某个元素的左边存在比它更大的元素，比如 1 10 5
// 5 这个元素的左边存在 10 这个元素比它更大，一定 5 要参与到排序里去的
// 如果某个元素的右边存在比它更小的元素，比如 1 10 5
// 10 这个元素的右边存在 5 这个元素比它更小，所以 10 一定要参与到排序里去的
// 所以我们只需要寻找最靠右的那个数（满足左边存在大于它的数）
// 和最靠左的那个数（满足右边存在小于它的数）
// 那么这两个数之间就是要排序的区间了
// 第一次遍历是从尾到头进行遍历，目的是为了找出最靠左的那个数，即满足右边存在小于它的数
// 一开始默认最右边的数为最小值
int min = array[array.size()-1];
// 默认找不到的情况下 m 为 -1
int m = -1;
// 从尾到头进行遍历，直到遍历到数组的开始位置
for(int i = array.size() - 2 ; i >= 0 ; i-- ){
// 获取当前遍历的元素值
int cur = array[i];
// 如果此时当前的元素值小于等于最小值，需要更新最小值
if(cur <= min){
// 更新最小值
min = cur;
}else{
// 如果当前元素大于了最小值，由于我们是从尾到头进行遍历，说明当前元素的右边存在小于它的数，这个元素需要加入到排序的区间
// 比如 10 9 7
// 最小值是 7 ，而 9 大于 7，所以 9 需要加入到排序的区间
// 因此更新 m 的值为 j，说明此时遍历的那些元素中 j 是最靠左的那个数
m = i;
}
}
// 第二次遍历是从尾到头进行遍历，目的是为了找出最靠右的那个数，即满足左边存在大于它的数
// 一开始默认最左边的数为最大值
int max = array[0];
// 默认找不到的情况下 n 为 -1
int n = -1;
for(int j = 1 ;j < array.size() ; j++ ){
// 获取当前遍历的元素值
int cur = array[j];
// 如果此时当前的元素值大于等于最大值，需要更新最大值
if(cur>=max){
// 更新最大值
max = cur;
}else{
// 如果当前元素小于了最大值，由于我们是从头到尾进行遍历，说明当前元素的左边存在大于它的数，这个元素需要加入到排序的区间
// 比如 10 9 7
// 最小值是 10 ，而 7 小于 10，所以 7 需要加入到排序的区间
// 因此更新 n 的值为 i，说明此时遍历的那些元素中 i 是最靠右的那个数
n = j;
}
}
// m 和 n 这两个数之间就是要排序的区间，返回即可
return {m,n};
}
};
3、Python 代码
部分排序 （面试题 16）:https://leetcode-cn.com/problems/sub-sort-lcci/
class Solution:
def subSort(self, array: List[int]) -> List[int]:
# 如果数组为空、或者数组没有元素、或者数组只有一个元素，找不出符合要求的序列，根据题目要求返回 [-1,-1]
if array == None or len(array) == 0 or len(array) == 1:
return [-1,-1]
# 正常来说，整个数组是递增有序的，比如 1 3 5 9 10 这种
# 如果某个元素的左边存在比它更大的元素，比如 1 10 5
# 5 这个元素的左边存在 10 这个元素比它更大，一定 5 要参与到排序里去的
# 如果某个元素的右边存在比它更小的元素，比如 1 10 5
# 10 这个元素的右边存在 5 这个元素比它更小，所以 10 一定要参与到排序里去的
# 所以我们只需要寻找最靠右的那个数（满足左边存在大于它的数）
# 和最靠左的那个数（满足右边存在小于它的数）
# 那么这两个数之间就是要排序的区间了
# 第一次遍历是从尾到头进行遍历，目的是为了找出最靠左的那个数，即满足右边存在小于它的数
# 一开始默认最右边的数为最小值
min = array[-1]
# 默认找不到的情况下 m 为 -1
m = -1
# 从尾到头进行遍历，直到遍历到数组的开始位置
j = len(array) - 2
while j >= 0:
# 获取当前遍历的元素值
cur = array[j]
# 如果此时当前的元素值小于等于最小值，需要更新最小值
if cur <= min:
# 更新最小值
min = cur
else:
# 如果当前元素大于了最小值，由于我们是从尾到头进行遍历，说明当前元素的右边存在小于它的数，这个元素需要加入到排序的区间
# 比如 10 9 7
# 最小值是 7 ，而 9 大于 7，所以 9 需要加入到排序的区间
# 因此更新 m 的值为 j，说明此时遍历的那些元素中 j 是最靠左的那个数
m = j
j -= 1
# 第二次遍历是从尾到头进行遍历，目的是为了找出最靠右的那个数，即满足左边存在大于它的数
# 一开始默认最左边的数为最大值
max = array[0]
# 默认找不到的情况下 n 为 -1
n = -1
# 从头进行遍历，直到遍历到数组的结束位置
i = 1
while i < len(array):
# 获取当前遍历的元素值
cur = array[i]
# 如果此时当前的元素值大于等于最大值，需要更新最大值
if cur >= max:
# 更新最大值
max = array[i]
else :
# 如果当前元素小于了最大值，由于我们是从头到尾进行遍历，说明当前元素的左边存在大于它的数，这个元素需要加入到排序的区间
# 比如 10 9 7
# 最小值是 10 ，而 7 小于 10，所以 7 需要加入到排序的区间
# 因此更新 n 的值为 i，说明此时遍历的那些元素中 i 是最靠右的那个数
n = i
i += 1
# m 和 n 这两个数之间就是要排序的区间，返回即可
return [m,n]
四、动画理解（没有声音）
隐藏内容
此处内容需要权限查看
