[CareerCup][Google Interview] 找出最小排序次数 - chkkch - 博客园

[CareerCup][Google Interview] 找出最小排序次数 - chkkch - 博客园
Given an unsorted array provide two indices n1 and n2 such that if we only sort the elements between n1 and n2,then the whole array will become sorted.
n1-n2 should be as minimum as possible.
http://www.careercup.com/question?id=4345015

就是找出左边的上升序列，然后在它右边找有没有小于它的，然后不断缩小上升序列的区间，直到序列右边没有小于它的值。

对于右边也找出上升序列，然后往左边找有没有大于它的，然后也不断缩小上升序列的区间。

这样两个区间的中间就是要排序的最小区间了。

5 void solve(vector<int> &a)
 6 {
 7     int i = 0;
 8     while(i < a.size() - 1)
 9     {
10         if (a[i] <= a[i+1])
11             i++;
12         else
13             break;
14     }
15 
16     int k = i + 1;
17 
18     while(i >= 0 && k < a.size())
19     {
20         if (a[k] < a[i])
21             i--;
22         else
23             k++;
24     }
25 
26     int j = a.size() - 1;
27 
28     while(j >= 1)
29     {
30         if (a[j-1] <= a[j])
31             j--;
32         else
33             break;
34     }
35 
36     k = j - 1;
37 
38     while(k > i && j < a.size())
39     {
40         if (a[k] > a[j])
41             j++;
42         else
43             k--;
44     }
45 
46     cout << i + 1 << ' ' << j - 1 << endl;
47 }

Read full article from [CareerCup][Google Interview] 找出最小排序次数 - chkkch - 博客园