17.6 Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence).
为了更好的理解题意，我们通过一个例子来分析，比如我们有如下的数组：
1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19
那么我们可以按照递增顺序将其分为三个部分：
left: 1, 2, 4, 7, 10, 11
middle: 7, 12
right: 6, 7, 16, 18, 19
只要从左右两端开始往中间搜索即可，遇到不是递增的数字就停止，然后我们要给中间的部分排序，排完序我们看left的最右边的数字是否比middle的最左边的数字小，right的最左边的数字是否比middle的最右边的数字大，如果不是，我们要shift_left和shift_right，向左边，我们再来验证整个数列是否是有序的，如果不是有序的，则说明不存在这样的index，参见代码如下：
int find_end_of_left_subsequence(vector<int> array) { for (int i = 1; i < array.size(); ++i) { if (array[i] < array[i - 1]) { return i - 1; } } return array.size() - 1; } int find_start_of_right_subsequence(vector<int> array) { for (int i = array.size() - 2; i >= 0; --i) { if (array[i] > array[i + 1]) { return i + 1; } } return 0; } int shrink_left(vector<int> array, int min_idx, int start) { int cmp = array[min_idx]; for (int i = start - 1; i >= 0; --i) { if (array[i] <= cmp) { return i + 1; } } return 0; } int shrink_right(vector<int> array, int max_idx, int start) { int cmp = array[max_idx]; for (int i = start; i < array.size(); ++i) { if (array[i] >= cmp) { return i - 1; } } return array.size() - 1; } bool validate(vector<int> array, int left_idx, int right_idx) { vector<int> middle(right_idx - left_idx + 1); for (int i = left_idx; i <= right_idx; ++i) { middle[i - left_idx] = array[i]; } sort(middle.begin(), middle.end()); for (int i = left_idx; i <= right_idx; ++i) { array[i] = middle[i - left_idx]; } for (int i = 1; i < array.size(); ++i) { if (array[i - 1] > array[i]) { return false; } } return true; } void find_unsorted_sequence(vector<int> array) { int end_left = find_end_of_left_subsequence(array); if (end_left >= array.size() - 1) return; int start_right = find_start_of_right_subsequence(array); int max_idx = end_left; int min_idx = start_right; for (int i = end_left + 1; i < start_right; ++i) { if (array[i] < array[min_idx]) { min_idx = i; } if (array[i] > array[max_idx]) { max_idx = i; } } int left_idx = shrink_left(array, min_idx, end_left); int right_idx = shrink_right(array, max_idx, start_right); if (validate(array, left_idx, right_idx)) { cout << "True: " << left_idx << " " << right_idx << endl; } else { cout << "False: " << left_idx << " " << right_idx << endl; } }
本文转自博客园Grandyang的博客，原文链接：排列数组[CareerCup] 17.6 Sort Array ，如需转载请自行联系原博主。
