【leetcode】面试题 16.16. 部分排序

╰半橙微兮° 2022-08-31 06:50 210阅读 0赞

### 面试题 16.16. 部分排序 ###

*  题目难度：中等
 *  方法一：双指针(找最大逆序对)

> 链接：[https://leetcode-cn.com/problems/sub-sort-lcci/][https_leetcode-cn.com_problems_sub-sort-lcci]  
> 来源：力扣（LeetCode）

# 题目难度：中等 #

给定一个整数数组，编写一个函数，找出索引`m`和`n`，只要将索引区间`[m,n]`的元素排好序，整个数组就是有序的。

注意：`n-m`尽量最小，也就是说，找出符合条件的最短序列。函数返回值为`[m,n]`，若不存在这样的`m`和`n`（例如整个数组是有序的），请返回`[-1,-1]`。

示例 1：

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
    输出： [3,9]

限制：

0 <= len(array) <= 1000000

# 方法一：双指针(找最大逆序对) #

找逆序对，什么是逆序对？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
比如一个单调递增的序列，里面出现了某几个递减的元素，那这几个元素就组成一个逆序对，`{5,4}`，`{5,3}`，`{5,2}` 都是逆序对，那么最大逆序对肉眼可见就是`{5,2}`

思路：找出`5,2`元素对应的索引

从左往右扫描，寻找逆序对（正序：逐渐变大）

*  定义一个变量，在遍历数组时，记录当前数组的最大值
 *  定义一个指针`r`，用于记录最大逆序对的右边界
 *  从左往右遍历，只要发现当前值大于等于最大值的，就用当前值替换最大值，始终保持`max`是最大的
 *  只要发现当前值小于最大值的 ，就用`r`记录它的索引位置，始终`r`位置的值小于最大值，这样遍历结束后，就找到了逆序对的右边界

从右往左扫描，寻找逆序对（正序：逐渐变小）

*  思路一样，和上面的寻找方式一样，只是符号相反

时间复杂度：o(n)  
空间复杂度：o(1)

public int[] subSort(int[] nums) {
        
        if (nums.length == 0) return new int[]{
        -1, -1};
    
        // 从左扫描到右寻找逆序对（正序：逐渐变大）
        int max = nums[0];
        int r = -1; // 用来记录最右的那个逆序对位置
        for (int i = 1; i < nums.length; i++) {
        
            if (nums[i] >= max) {
        
                max = nums[i];
            } else {
        
                r = i;
            }
        }
    
        // 提前结束
        if (r == -1) return new int[]{
        -1, -1};
    
        // 从右扫描到左寻找逆序对（正序：逐渐变小）
        int min = nums[nums.length - 1];
        int l = -1; // 用来记录最左的那个逆序对位置
        for (int i = nums.length - 2; i >= 0; i--) {
        
            if (nums[i] <= min) {
        
                min = nums[i];
            } else {
        
                l = i;
            }
        }
    
        return new int[]{
        l, r};
    }

def subSort(self, nums: List[int]) -> List[int]:
        if len(nums) == 0:
            return [-1, -1]
    
        nums_max = nums[0]
        r = -1
        for i in range(1, len(nums)):
            if nums[i] >= nums_max:
                nums_max = nums[i]
            else:
                r = i
    
        if r == -1:
            return [-1, -1]
    
        nums_min = nums[len(nums) - 1]
        l = -1
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] <= nums_min:
                nums_min = nums[i]
            else:
                l = i
    
        return [l, r]

[https_leetcode-cn.com_problems_sub-sort-lcci]: https://leetcode-cn.com/problems/sub-sort-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20220829/b19d78dbcec849e7b2c4fcf2563f56c1.png