首页 > 编程语言 > 详细

最短需排序子数组的长度

时间:2020-02-23 19:15:00      阅读:20      评论:0      收藏:0      [点我收藏+]

标签:spa   所在   乱序   min   code   方法   

题意:给出一个数组,如 [1,4,6,5,9,10] , 如果将6,5进行从小至大排序,那么就能够得到一个有序序列,而且这个是最小的需排序单元,长度为2。

 

这个问题如果用一般的方法想,很复杂。

注意接下来介绍的性质:如果一个数组是有序的(假设从小至大),那么,遍历每个元素arr[i]<=arr[i+1],或者这样说 max { arr[1] , arr[2] , ... ,arr[i] } <= arr[i+1];如果一个点, max { arr[1] , arr[2] , ... ,arr[i] } <= arr[i+1] <= min { arr[i+2] , arr[i+3] ,... arr[n] } ;那么该点所在的位置肯定是没错的,称为正常点,否则称为乱序点,但是它仍然可能在乱序区间内。

因此,我们只需要找到最左边和最右边的乱序点,然后计算长度,即可。

 

tips:如果没告知你是从小至大有序还是从大至小有序,那么都需要考虑。

 

 1 // 这里只考虑从小至大的情况
 2 
 3 int GetNonSortMinLen(vector<int> v){
 4     if(v.size()<=1){
 5         return 0;
 6     }    
 7     int tmp_min=v[0];
 8     int tmp_max=v[v.size()-1];
 9     int min_idx=0;
10     int max_idx=v.size()-1;
11     for(int i=1;i<v.size();i++){
12         if(v[i]>=tmp_min){
13             tmp_min=v[i];
14         }
15         else{
16             min_idx=i;
17         }
18     }
19     for(int i=v.size()-2;i>-1;i--){
20         if(v[i]<=tmp_max){
21             tmp_max=v[i];
22         }
23         else{
24             max_idx=i;
25         }
26     }
27     if(min==0){
28         return 0;
29     }
30     return min_idx-max_idx+1;
31 }

 

最短需排序子数组的长度

标签:spa   所在   乱序   min   code   方法   

原文:https://www.cnblogs.com/yy-1046741080/p/12353178.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号