【搞定算法】需要排序的最短子数组长度

水深无声 2021-11-23 01:46 228阅读 0赞

> **题目：给定一个无序数组 arr，求出需要排序的最短子数组长度。例如：arr = \[1，5，3，4，2，6，7\] 返回 4，因为只有 \[5，3，4，2\] 需要排序。**
> 
> 要求：时间复杂度 O(N)、额外空间复杂度O(1)。

假设数组为 \[a b c d e f g h i j k l m n\]，如果 abc 是有序的，mn是 有序的，至于中间的 defghijkl 是无序的，我们可以得知，如果是正常升序序列，左边的一定是小于右边的任意数值，右边的一定大于左边的任意数值。

**分析：**

**分别从左往右和从右往左遍历，找出左右两边失效的位置，则这两个失效位置中间的数组即为需要排序的最短子数组。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

**步骤：**

1、从左向右遍历，找出不合适数的最右范围：从左往右遍历，如果 maxLeft > 当前元素，则记录它的位置到 invalidRight ，一直遍历到最右边【可知 invalidRight 是最后一个不满足排序要求的数，其右边都满足大于 invalidRight 】

2、从右向左遍历，找出不合适数的最左范围：从右往左遍历，如果当前元素 > minRight，则记录它的位置为 invalidLeft，一直遍历到最左边 【可知 invalidLeft 是最后一个不满足排序要求的数，其左边都满足小于 minRight】

3、invalidRight - invalidLeft + 1 就是需要排序的最短子数组长度。

public class GetMinLengthForSort {
    
        public static int getMinLengthForSort(int[] arr){
            if(arr == null || arr.length < 2){
                return 0;   // 不需要排序
            }
    
            int maxLeft = arr[0];  // 左边最大
            int minRight = arr[arr.length - 1];  // 右边最小
            // 这两个指针分别记录左右两边无效的位置
            int invalidLeft = 0;
            int invalidRight = -1;  // 数组原本有序时：invalidRight - invalidLeft + 1 = 0
            // 1、从左到右遍历：找出不合适数的最右范围
            // 遍历过的最大值大于当前值，那么当前值肯定是无效的，那么排序时这个最大值在当前位置或者是更右的位置
            for(int i = 1; i < arr.length; i++){
                if(maxLeft > arr[i]){
                    // 如果已经遍历过的最大值大于当前值，则记录最右边无效位置
                    invalidRight = i;
                }else{
                    // 如果已经遍历过的最大值小于等于当前值，则遍历过的最大值更新为当前值
                    maxLeft = arr[i];
                }
            }
            // 2、从右向左遍历：找出不合适数的最左范围
            // 遍历过的最小值小于当前值，那么当前值就是无效的，那么排序时这个最小值在当前位置或者是更左的位置
            for(int i = arr.length - 2; i >= 0; i--){
                if(minRight < arr[i]){
                    // 如果已经遍历的最小值小于当前值，则记录最左边无效的位置
                    invalidLeft = i;
                }else{
                    // 更新最小值
                    minRight = arr[i];
                }
            }
            // invalidRight是不合适数的最右范围，invalidLeft 是不合适数的最左范围
            // invalidRight - invalidLeft + 1 就是不合适数的个数
            return invalidRight - invalidLeft + 1;
        }
    
        public static void main(String[] args) {
            int[] arr = {1,2,3,4,5,6};
            System.out.println(getMinLengthForSort(arr));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20211122/236d8527d4704d5296f0468c410b1a7e.png