【数组】面试题 16.16. 部分排序
2021-01-29 14:14
标签：判断 array 扫描 min 完成 解答 原理 一点 ima 题目： 解答： 默认升序（降序也只是改一点代码，不影响） 原理：如果左侧最大值大于中间的最小值，则一定会被中间序列包括；同理，如果右侧最小值大于中间的最大值，则一定会被中间序列包括。 一遍遍历 + 两个指针（两次扫描可一次遍历完成） 1、从前向后扫描数组，判断当前array[i]是否比max小，是则将last置为当前array下标i，否则更新max; 2、从后向前扫描数组，判断当前array[len - 1 - i]是否比min大，是则将first置位当前下标len - 1 - i，否则更新min; 3、返回{first， last} 【数组】面试题 16.16. 部分排序 标签：判断 array 扫描 min 完成 解答 原理 一点 ima 原文地址：https://www.cnblogs.com/ocpc/p/12832054.html
1 class Solution {
2 public:
3 vectorint> subSort(vectorint>& array)
4 {
5 if (array.size() == 0)
6 {
7 return {-1, -1};
8 }
9
10 int last = -1;
11 int first = -1;
12
13 int max = INT_MIN;
14 int min = INT_MAX;
15
16 int len = array.size();
17
18 for (int i = 0; i )
19 {
20 if (array[i] max)
21 {
22 last = i;
23 }
24 else
25 {
26 max = std::max(max, array[i]);
27 }
28
29 if (array[len - 1 -i] > min)
30 {
31 first = len - 1 - i;
32 }
33 else
34 {
35 min = std::min(min, array[len - 1 - i]);
36 }
37 }
38
39 return {first, last};
40 }
41 };
上一篇：Springboot的多环境配置
下一篇：数据结构与算法参考答案（第二周）
文章标题：【数组】面试题 16.16. 部分排序
文章链接：http://soscw.com/index.php/essay/48713.html