网站后台一般是用什么做的,贵阳网络科技有限公司,人力外包公司有哪些,旅游景区宣传软文文章目录1. 题目2. 解题2.1 排序2.2 不排序1. 题目
给定一个整数数组#xff0c;编写一个函数#xff0c;找出索引 m 和 n #xff0c;只要将索引区间 [m,n] 的元素排好序#xff0c;整个数组就是有序的。 注意#xff1a;n-m 尽量最小#xff0c;也就是说#xff0c;找…
文章目录1. 题目2. 解题2.1 排序2.2 不排序1. 题目
给定一个整数数组编写一个函数找出索引 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/sub-sort-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 排序
复制一份原数组对复制数组排序将两个数组对比看不同的部分是什么区间即可
class Solution {
public:vectorint subSort(vectorint array) {vectorint sortArray(array);sort(sortArray.begin(), sortArray.end());vectorint ans;int i 0;while(i array.size() array[i]sortArray[i])i;if(i array.size())ans.push_back(i);i array.size()-1;while(i 0 array[i]sortArray[i])--i;if(i 0)ans.push_back(i);if(ans.size()2)return ans;return {-1,-1};}
};472 ms 40.4 MB
2.2 不排序
从左往右遍历左边最大MAX 当前数这里肯定需要排序实时更新MAX找到需要排序的右端点从右往左遍历当前数 右边最小MIN肯定需要排序实时更新MIN往左找到左端点
class Solution {
public:vectorint subSort(vectorint array) {if(array.size() 2)return {-1,-1};int lmax array[0], rmin array[array.size()-1];int left -1, right -1, n array.size();for(int i 1; i n; i){if(array[i] lmax){right i;}lmax max(lmax, array[i]);if(array[n-1-i] rmin){left n-i-1;}rmin min(rmin, array[n-1-i]);}return {left, right};}
};156 ms 39.1 MB
