首页 > 代码库 > careercup-中等难度 17.6
careercup-中等难度 17.6
17.6 给定一个整数数组，编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n越小越好，也就是说，找出符合条件的最短序列。
解法：
开始解题之前，让我们先确认一下答案会是什么样的。如果要找的是两个索引，这表明数组中间有一段有待排序，其中数组开头和末尾部分是排好序的。
现在，我们借用下面的例子来解决此题：
1,2,4,7,10,11,7,12,6,7,16,18,19
首先映入脑海的想法可能是，直接找出位于开头的最长递增子序列，以及位于末尾的最长递增子序列。
左边：1,2,4,7,10,11
中间：7,12
右边：6,7,16,18,19
很容易就能找出这些子序列，只需从数组最左边和最右边开始，向中间查找递增子序列。一旦发现元素大小顺序不对，那就是找到了递增/递减子序列的两头。
但是，为了解决这个问题，还需要对数组中间部分进行排序，只要将中间部分排好序，数组所有元素便是有序的。具体来说，就是一下判断条件必须为真：
//左边所有元素都要小于中间所有元素
min(middle)>end(left)
//中间所有元素都要小于右边的所有元素
max(middle)<start(right)
或者，换句话说，对于所有元素：
left<middle<right
实际上，上例的这个条件绝对不可能成立。根据定义，中间部分的元素是无序的。而在上面的例子中，left.end>middle.start且middle.end>right.start一定成立。这样一来，只排序中间部分并不能让整个数组有序。
不过，我们还可以缩减左边和右边的子序列，直到先前的条件成立为止。
令min等于min(middle)，max等于max(middle).
对左边部分，我们先从这个子序列的末尾开始，并向左移动，直到找到元素索引i使得array[i]<min;找到后只需排序中间部分，就能让数组的那部分有序。
然后，对右边部分进行类似操作。
C++实现代码：
#include<iostream>using namespace std;int findEndOfLeftSubsequence(int array[],int n){ int i; for(i=1;i<n;i++) { if(array[i]<array[i-1]) return i-1; } return n-1;}int findEndOfRightSubsequence(int array[],int n){ int i; for(i=n-2;i>=0;i--) { if(array[i]>array[i+1]) return i+1; } return 0;}int shrinkLeft(int array[],int n,int min_index,int start){ int comp=array[min_index]; cout<<comp<<endl; int i; for(i=start-1;i>=0;i--) { if(comp>=array[i]) return i+1; } return 0;}int shrinkRight(int array[],int n,int max_index,int start){ int comp=array[max_index]; cout<<comp<<endl; for(int i=start;i<n;i++) { if(comp<=array[i]) return i-1; } return n-1;}void findUnsortedSequence(int array[],int n){ int end_left=findEndOfLeftSubsequence(array,n); cout<<end_left<<endl; int start_right=findEndOfRightSubsequence(array,n); cout<<start_right<<endl; int min_index=end_left+1; if(min_index>=n) return; int max_index=start_right-1; for(int i=end_left;i<=start_right;i++) { if(array[i]<array[min_index]) min_index=i; if(array[i]>array[max_index]) max_index=i; } cout<<array[min_index]<<" "<<array[max_index]<<endl; int right_index=shrinkRight(array,n,max_index,start_right); int left_index=shrinkLeft(array,n,min_index,end_left); cout<<left_index<<" "<<right_index<<endl;}int main(){ int arr[12]={1,2,4,7,10,7,12,6,7,16,18,19}; findUnsortedSequence(arr,12);}
careercup-中等难度 17.6