题目链接
LeetCode 面试题 16.16. 部分排序[1]
题目描述
给定一个整数数组,编写一个函数,找出索引 m
和 n
,只要将索引区间 [m, n]
的元素排好序,整个数组就是有序的。注意:n-m
尽量最小,也就是说,找出符合条件的最短序列。函数返回值为 [m, n]
,若不存在这样的 m
和 n
(例如整个数组是有序的),请返回 [-1, -1]
。
示例1
输入:[1,2,4,7,10,11,7,12,6,7,16,18,19]输出:[3,9]
说明:
0 <= len(array) <= 1000000
题解
首先虽然题目没说,但是实际运行下来数列是单调递增的,所以我们下面默认数列是递增的。
那么对于元素 a[i]
来说,如果它左边存在大于 a[i]
的元素,那么 a[i]
是一定要参与到排序里去的。或者说如果它右边存在小于 a[i]
的元素,那么 a[i]
也是要参与到排序里去的。
所以我们只需要寻找最靠右的那个数(满足左边存在大于它的数),和最靠左的那个数(满足右边存在小于它的数),那么这两个数之间就是要排序的区间了。
为什么最靠右的那个(满足左边存在大于它的数)数一定能保证右边没有更小的数了呢?因为如果右边还有更小的数,那么那个更小的数才是更靠右的啊,这就矛盾了。
所以我们只需要从左到右扫描一遍,用一个变量维护一下最大值就行了,然后反向再遍历一遍,维护一个最小值。
代码
c++
classSolution { public: vector<int>subSort(vector<int>&array) { intn=array.size(); intmaxx=INT_MIN, minn=INT_MAX; intl=-1, r=-1; for (inti=0; i<n; ++i) { if (array[i] <maxx) r=i; elsemaxx=array[i]; } for (inti=n-1; i>=0; --i) { if (array[i] >minn) l=i; elseminn=array[i]; } return {l, r}; } };
python
classSolution: defsubSort(self, array: List[int]) ->List[int]: n=len(array) maxx, minn=-10000000, 10000000l, r=-1, -1foriinrange(n): ifarray[i] <maxx: r=ielse: maxx=array[i] foriinrange(n-1, -1, -1): ifarray[i] >minn: l=ielse: minn=array[i] return [l, r]
参考资料
[1]
LeetCode 面试题 16.16. 部分排序: https://leetcode-cn.com/problems/sub-sort-lcci/
作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~