《Cracking the Coding Interview》——第17章：普通题——题目6

 1 // 17.6 Given an array, if you sort a subarray of it, the total array will become sorted. Find the length of the shortest of all such subarrays.
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 
 6 void findUnsortedSequence(vector<int> &v, int &left_index, int &right_index)
 7 {
 8     int n = v.size();
 9     
10     left_index = right_index = -1;
11     if (n < 2) {
12         return;
13     }
14     int val;
15     int i;
16     
17     val = v[0];
18     for (i = 1; i <= n - 1; ++i) {
19         val = v[i] > val ? v[i] : val;
20         if (v[i] < val) {
21             right_index = i;
22         }
23     }
24     
25     val = v[n - 1];
26     for (i = n - 2; i >= 0; --i) {
27         val = v[i] < val ? v[i] : val;
28         if (v[i] > val) {
29             left_index = i;
30         }
31     }
32 }
33 
34 int main()
35 {
36     vector<int> v;
37     int i;
38     int n;
39     int left_index, right_index;
40     
41     while (scanf("%d", &n) == 1 && n > 0) {
42         v.resize(n);
43         for (i = 0; i < n; ++i) {
44             scanf("%d", &v[i]);
45         }
46         findUnsortedSequence(v, left_index, right_index);
47         printf("(%d, %d)\n", left_index, right_index);
48         v.clear();
49     }
50     
51     return 0;
52 }