class Solution {
public:
vector<int> subSort(vector<int>& array) {
}
};
面试题 16.16. 部分排序
给定一个整数数组，编写一个函数，找出索引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原站题解
python3 解法, 执行用时: 104 ms, 内存消耗: 31.1 MB, 提交时间: 2022-11-30 22:12:21
class Solution:
def subSort(self, array: List[int]) -> List[int]:
n = len(array)
res = [-1, -1]
if n <= 1: return res
_max, _min = array[0], array[n - 1]
for i in range(n):
j = n - 1 - i
if array[i] < _max:
res[0] = i
else:
_max = array[i]
if array[j] > _min:
res[1] = j
else:
_min = array[j]
return sorted(res)
python3 解法, 执行用时: 84 ms, 内存消耗: 31.1 MB, 提交时间: 2022-11-30 21:59:55
class Solution:
def subSort(self, array: List[int]) -> List[int]:
a=array[:]
a.sort()
if a==array:
return [-1,-1]
n=len(array)
i=0
j=n-1
while a[i]==array[i]:
i+=1
while a[j]==array[j]:
j-=1
return [i,j]
java 解法, 执行用时: 3 ms, 内存消耗: 65.3 MB, 提交时间: 2022-11-30 21:59:02
class Solution {
public int[] subSort(int[] array) {
if(array == null || array.length == 0) return new int[]{-1, -1};
int last = -1, first = -1;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int len = array.length;
for(int i = 0; i < len; i++){
if(array[i] < max){
last = i;
}else{
max = Math.max(max, array[i]);
}
if(array[len - 1 - i] > min){
first = len - 1 - i;
}else{
min = Math.min(min, array[len - 1 - i]);
}
}
return new int[] {first, last};
}
}