数组中最短无序序列

快来打我* 2022-06-07 03:53 141阅读 0赞

题目描述：

> 给定一个整数数组，编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m越小越好，也就是说，找出符合条件的最短序列。

示例：

> 输入：1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19  
> 输出：(3, 9)

**解法：**  
题目的要求是要找出两个索引，这表明数组中间有一段数据有待排序，其中数组开头和末尾是排好序的。容易想到的是，直接找出位于开头的最长递增子序列，以及位于末尾的最长递增子序列。于是：

> 左边：1, 2, 4, 7, 10, 11  
> 中间：7, 12  
> 右边：6, 7, 16, 18, 19

很容易就能找出这些子序列，只需从数组最左边和最右边开始分别扫描，向中间查找递增子序列。一旦发现有元素大小顺序不对，那就是找到了递增子序列的两端。但是，为了解决这个问题，还需要对数组中间部分进行排序，只要将中间部分排好序，数组所有元素便是有序的。具体来说，就是一下判断条件必须为真：

> /\* 左边（left）所有元素都要小于中间（middle）的所有元素\*/  
> min(middle) > end(left)
> 
> /\* 中间（middle）所有元素都要小于右边（right）的所有元素\*/  
> max(middle) < start(right)

但是在上面的例子中可以看出，min(middle) > end(left)或max(middle) < start(right)并不一定总能满足。因此，需要缩减左边和右边的子序列，直到先前的条件成立为止。

令min等于min(middle)，max等于max(middle)。  
对于左边部分：我们先从子序列的末尾开始（值11，索引为5），并向左移动，直至找到元素索引i使得aray\[i\] < min；找到后只需排序中间部分，就能让数组的那部分有序。

对于右边部分：进行类似左边的操作，此时max等于12，,我们先从右边子序列的起始元素（值为6）开始，并向右移动，将中间部分的最大值12依次与6,7,16比较。找到16时，就能确定16的右边已经没有元素比12小了（因为右边是递增子序列）。至此，对数组中间部分进行排序，以使整个数组都是有序的。

下面是算法的实现代码：

public class PartialSortedSeq {
    
        public static void main(String[] args) {
            PartialSortedSeq partialSortedSeq = new PartialSortedSeq();
            int[] arr = {
       1,2,7,4,10,11,7,12,6,7,16,18,19};
            partialSortedSeq.findUnsortedSequene(arr);
        }
    
        public void findUnsortedSequene(int[] arr) {
            /*找出左连续子序列*/
            int end_left = 0;
            for(int i = 1; i < arr.length; i++) {
                if (arr[i] > arr[i-1]) {
                    end_left = i;
                } else {
                    break;
                }
            }
    
            /*找出右连续子序列*/
            int start_right = arr.length - 1;
            for(int i = arr.length-2; i >= 0; i--) {
                if (arr[i] < arr[i+1]) {
                    start_right = i;
                } else {
                    break;
                }
            }
    
            /*找出中间部分的最大值和最小值*/
            int min_index = end_left + 1;
            int max_index = start_right - 1;
            for(int i = min_index+1; i <= start_right-1; i++) {
                if (arr[i] < arr[min_index]) {
                    min_index = i;
                }
                if (arr[i] > arr[max_index]) {
                    max_index = i;
                }
            }
    
            int left_index = 0;
            /*向左移动，直到小于arr[min_index]*/
            for(int i = end_left; i >= 0; i--) {
                int comp = arr[min_index];
                if (arr[i] >= comp) {
                    left_index = i;
                } else {
                    break;
                }
            }
    
            int right_index = arr.length - 1;
            /*向右移动，直到大于arr[max_index]*/
            for(int i = start_right; i < arr.length; i++) {
                int comp = arr[max_index];
                if (arr[i] <= comp) {
                    right_index = i;
                } else {
                    break;
                }
            }
    
            System.out.println(left_index + "," + right_index);
        }
    }