算法——最小调整有序

原创
2016/11/26 09:51
阅读数 200

题目描述
有一个整数数组,请编写一个函数,找出索引m和n,只要将m和n之间的元素排好序,整个数组就是有序的。注意:n-m应该越小越好,也就是说,找出符合条件的最短序列。
给定一个int数组A和数组的大小n,请返回一个二元组,代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序,返回[0,0])。保证A中元素均为正整数。
测试样例:
[1,4,6,5,9,10],6
返回:[2,3]

解法:
另外申请一个等大数组tags,用来记录边界位置。
首先从左往右遍历一遍,使用max变量记录当前下标以左的最大值,并使用max与当前值比较,如果max>当前值,则记录当前下标;
再从右往左遍历一遍,类似地,用min变量记录当前下标以右的最小值,并使用min与当前值比较,如果min<当前值,则记录当前下标;

通过以上两次遍历可以分别得到最右标记下标和最左标记下标,则这两个下标即为所求下标。

原理:
通过两次遍历,标记的下标均为在其遍历方向上的逆序对的最远位置。因此逆序最远截止于次,所以这两个下标可以代表所需调整的最短的一段。

代码:

public int[] findSegment(int[] A, int n) {
        if(A==null || n==1)
            return new int[]{0,0};
        boolean[] tags = new boolean[n];
        int max = A[0];
        for(int i=1;i<n;i++){
            if(max>A[i]){
                tags[i] = true;
            }
            max = max<A[i]?A[i]:max;
        }
        int right = -1;
        for(int i=0;i<n;i++){
            right = tags[i]?i:right;
            tags[i] = false;
        }


        int min = A[n-1];
        for(int i=n-2;i>=0;i--){
            if(min<A[i]){
                tags[i] = true;
            }
            min = min>A[i]?A[i]:min;
        }
        int left = n;
        for(int i=n-1;i>=0;i--){
            left = tags[i]?i:left;
        }

        if(left==n){
            left = 0;
            right = 0;
        }
        return new int[]{left,right};
    }

 

方法1:

 

[cpp] view plain copy

在CODE上查看代码片派生到我的代码片

  1. class Rearrange  
  2. {  
  3. public:  
  4.     vector<int> findSegment(vector<int> A, int n)  
  5.     {  
  6.         //排序后查找不同的位置  
  7.         // write code here  
  8.         vector<int> v=A;  
  9.         sort(v.begin(),v.end());  
  10.         int low=0,high=0;  
  11.         for(int i=0;i<A.size();i++)  
  12.         {  
  13.             if(A[i]!=v[i])  
  14.             {  
  15.                 low=i;  
  16.                 break;  
  17.             }  
  18.         }  
  19.         for(int i=A.size()-1;i>=0;i--)  
  20.         {  
  21.             if(A[i]!=v[i])  
  22.             {  
  23.                 high=i;  
  24.                 break;  
  25.             }  
  26.         }  
  27.         vector<int> result;  
  28.         result.push_back(low);  
  29.         result.push_back(high);  
  30.         return result;  
  31.     }  
  32. };  

方法2:

 

 

进行两次遍历,一次从左到右找出N,一次从右到左找出M

(1)从左到右找出N

如果当前元素小于之前的最大元素则说明当前元素应处于[M N]无序序列中而且当前元素是当前最大下标的无序元素所以更新N为当前元素下标。

(2)从右到左找出M

如果当前元素大于之前的最小元素则说明当前元素应处于[M N]无序序列中而且当前元素是当前最小下标的无序元素所以更新M为当前元素下标

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部