部分排序 (面试题 16)

本文内容为算法训练营一期内容,仅限训练营学员观看

一、题目描述

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

注意:n – m 尽量最小,也就是说,找出符合条件的最短序列。

函数返回值为 [m,n] ,若不存在这样的 m 和 n(例如整个数组是有序的),请返回 [-1,-1] 。

二、题目解析

对于元素 a[i] 来说,如果它左边存在大于 a[i] 的元素,那么 a[i] 是一定要加入到被排序的序列内

如果它右边存在小于 a[i] 的元素,那么a[i]` 也要加入到被排序的序列内

所以,我们的目的很明确。

1、寻找最靠右的那个数,即它的左边存在大于它的数

2、寻找最靠左的那个数,即它的右边存在小于它的数

这两个数之间就是要排序的区间

最靠右的数具备以下特征:

1、它的左边存在大于它的数

2、它的右边数都比它更大

3、相对于多个符合 1、2 要求的数,它是最靠右的

同样的,最靠左的数具备以下特征:

1、它的右边存在小于它的数

2、它的左边数都比它更小

3、相对于多个符合 1、2 要求的数,它是最靠左的

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 部分排序 (面试题 16):https://leetcode-cn.com/problems/sub-sort-lcci/ 
class Solution {
    public int[] subSort(int[] array) {

        // 如果数组为空、或者数组没有元素、或者数组只有一个元素,找不出符合要求的序列,根据题目要求返回 [-1,-1]
        if(array == null || array.length == 0 || array.length == 1) return new int[]{-1,-1};

        // 正常来说,整个数组是递增有序的,比如 1 3 5 9 10 这种
        // 如果某个元素的左边存在比它更大的元素,比如  1 10 5  
        // 5 这个元素的左边存在 10 这个元素比它更大,一定 5 要参与到排序里去的

        // 如果某个元素的右边存在比它更小的元素,比如  1 10 5  
        // 10 这个元素的右边存在 5 这个元素比它更小,所以 10 一定要参与到排序里去的

        // 所以我们只需要寻找最靠右的那个数(满足左边存在大于它的数)
        // 和最靠左的那个数(满足右边存在小于它的数)
        // 那么这两个数之间就是要排序的区间了

        // 第一次遍历是从尾到头进行遍历,目的是为了找出最靠左的那个数,即满足右边存在小于它的数

        // 一开始默认最右边的数为最小值
        int min = array[array.length - 1];

        // 默认找不到的情况下 m 为 -1
        int m = -1;

        // 从尾到头进行遍历,直到遍历到数组的开始位置
        for( int j = array.length - 2 ; j >= 0 ; j-- ){
            // 获取当前遍历的元素值
            int cur = array[j] ;
            // 如果此时当前的元素值小于等于最小值,需要更新最小值
            if(cur <= min){
                // 更新最小值
                min = cur;
            }else{
                // 如果当前元素大于了最小值,由于我们是从尾到头进行遍历,说明当前元素的右边存在小于它的数,这个元素需要加入到排序的区间
                // 比如  10 9 7
                // 最小值是 7 ,而 9 大于 7,所以 9 需要加入到排序的区间
                // 因此更新 m 的值为 j,说明此时遍历的那些元素中 j 是最靠左的那个数
                m = j;
            }
        }


        // 第二次遍历是从尾到头进行遍历,目的是为了找出最靠右的那个数,即满足左边存在大于它的数

        // 一开始默认最左边的数为最大值
        int max = array[0];

        // 默认找不到的情况下 n 为 -1
        int n = -1;

        // 从头进行遍历,直到遍历到数组的结束位置
        for( int i = 1 ; i < array.length ; i++ ){
            // 获取当前遍历的元素值
            int cur = array[i] ;
            // 如果此时当前的元素值大于等于最大值,需要更新最大值
            if(cur >= max){
                // 更新最大值
                max = array[i];
            }else{
                // 如果当前元素小于了最大值,由于我们是从头到尾进行遍历,说明当前元素的左边存在大于它的数,这个元素需要加入到排序的区间
                // 比如  10 9 7
                // 最小值是 10 ,而 7 小于 10,所以 7 需要加入到排序的区间
                // 因此更新 n 的值为 i,说明此时遍历的那些元素中 i 是最靠右的那个数
                n = i;
            }
        }


        // m 和 n 这两个数之间就是要排序的区间,返回即可
        return new int[]{m,n};

    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 部分排序 (面试题 16):https://leetcode-cn.com/problems/sub-sort-lcci/ 
class Solution {
public:
    vector<int> subSort(vector<int>& array) {
        // 如果数组为空、或者数组没有元素、或者数组只有一个元素,找不出符合要求的序列,根据题目要求返回 [-1,-1]
        if(array.size()==0 || array.size()==1){
            return {-1,-1};
        }
        // 正常来说,整个数组是递增有序的,比如 1 3 5 9 10 这种
        // 如果某个元素的左边存在比它更大的元素,比如  1 10 5  
        // 5 这个元素的左边存在 10 这个元素比它更大,一定 5 要参与到排序里去的

        // 如果某个元素的右边存在比它更小的元素,比如  1 10 5  
        // 10 这个元素的右边存在 5 这个元素比它更小,所以 10 一定要参与到排序里去的

        // 所以我们只需要寻找最靠右的那个数(满足左边存在大于它的数)
        // 和最靠左的那个数(满足右边存在小于它的数)
        // 那么这两个数之间就是要排序的区间了

        // 第一次遍历是从尾到头进行遍历,目的是为了找出最靠左的那个数,即满足右边存在小于它的数

        // 一开始默认最右边的数为最小值
        int min = array[array.size()-1];

        // 默认找不到的情况下 m 为 -1
        int m = -1;

        // 从尾到头进行遍历,直到遍历到数组的开始位置
        for(int i = array.size() - 2 ; i >= 0 ; i-- ){
            // 获取当前遍历的元素值
            int cur = array[i];
            // 如果此时当前的元素值小于等于最小值,需要更新最小值
            if(cur <= min){
                // 更新最小值
                min = cur;
            }else{
                // 如果当前元素大于了最小值,由于我们是从尾到头进行遍历,说明当前元素的右边存在小于它的数,这个元素需要加入到排序的区间
                // 比如  10 9 7
                // 最小值是 7 ,而 9 大于 7,所以 9 需要加入到排序的区间
                // 因此更新 m 的值为 j,说明此时遍历的那些元素中 j 是最靠左的那个数
                m = i;
            }
        }
        // 第二次遍历是从尾到头进行遍历,目的是为了找出最靠右的那个数,即满足左边存在大于它的数

        // 一开始默认最左边的数为最大值
        int max = array[0];

        // 默认找不到的情况下 n 为 -1
        int n = -1;
        for(int j = 1 ;j < array.size() ; j++ ){
            // 获取当前遍历的元素值
            int cur = array[j];
            // 如果此时当前的元素值大于等于最大值,需要更新最大值
            if(cur>=max){
                // 更新最大值
                max = cur;
            }else{
                // 如果当前元素小于了最大值,由于我们是从头到尾进行遍历,说明当前元素的左边存在大于它的数,这个元素需要加入到排序的区间
                // 比如  10 9 7
                // 最小值是 10 ,而 7 小于 10,所以 7 需要加入到排序的区间
                // 因此更新 n 的值为 i,说明此时遍历的那些元素中 i 是最靠右的那个数
                n = j;
            }
        }
        // m 和 n 这两个数之间就是要排序的区间,返回即可
        return {m,n};

    }
};

3、Python 代码

部分排序 (面试题 16):https://leetcode-cn.com/problems/sub-sort-lcci/ 
class Solution:
    def subSort(self, array: List[int]) -> List[int]:
        # 如果数组为空、或者数组没有元素、或者数组只有一个元素,找不出符合要求的序列,根据题目要求返回 [-1,-1]
        if array == None or len(array) == 0 or len(array) == 1:
           return [-1,-1]

        # 正常来说,整个数组是递增有序的,比如 1 3 5 9 10 这种
        # 如果某个元素的左边存在比它更大的元素,比如  1 10 5  
        # 5 这个元素的左边存在 10 这个元素比它更大,一定 5 要参与到排序里去的

        # 如果某个元素的右边存在比它更小的元素,比如  1 10 5  
        # 10 这个元素的右边存在 5 这个元素比它更小,所以 10 一定要参与到排序里去的

        # 所以我们只需要寻找最靠右的那个数(满足左边存在大于它的数)
        # 和最靠左的那个数(满足右边存在小于它的数)
        # 那么这两个数之间就是要排序的区间了

        # 第一次遍历是从尾到头进行遍历,目的是为了找出最靠左的那个数,即满足右边存在小于它的数

        # 一开始默认最右边的数为最小值
        min = array[-1]

        # 默认找不到的情况下 m 为 -1
        m = -1


        # 从尾到头进行遍历,直到遍历到数组的开始位置
        j = len(array) - 2

        while j >= 0:
            # 获取当前遍历的元素值
            cur = array[j]       
            # 如果此时当前的元素值小于等于最小值,需要更新最小值
            if cur <= min:
                # 更新最小值
                min = cur
            else:
                # 如果当前元素大于了最小值,由于我们是从尾到头进行遍历,说明当前元素的右边存在小于它的数,这个元素需要加入到排序的区间
                # 比如  10 9 7
                # 最小值是 7 ,而 9 大于 7,所以 9 需要加入到排序的区间
                # 因此更新 m 的值为 j,说明此时遍历的那些元素中 j 是最靠左的那个数
                m = j

            j -= 1

        # 第二次遍历是从尾到头进行遍历,目的是为了找出最靠右的那个数,即满足左边存在大于它的数

        # 一开始默认最左边的数为最大值
        max = array[0]

        # 默认找不到的情况下 n 为 -1
        n = -1

        # 从头进行遍历,直到遍历到数组的结束位置
        i = 1
        while i < len(array):
            # 获取当前遍历的元素值
            cur = array[i] 
            # 如果此时当前的元素值大于等于最大值,需要更新最大值
            if cur >= max:
                # 更新最大值
                max = array[i]
            else :
                # 如果当前元素小于了最大值,由于我们是从头到尾进行遍历,说明当前元素的左边存在大于它的数,这个元素需要加入到排序的区间
                # 比如  10 9 7
                # 最小值是 10 ,而 7 小于 10,所以 7 需要加入到排序的区间
                # 因此更新 n 的值为 i,说明此时遍历的那些元素中 i 是最靠右的那个数
                n = i
            i += 1

        # m 和 n 这两个数之间就是要排序的区间,返回即可
        return [m,n]

四、动画理解(没有声音)

隐藏内容
  • 普通用户购买价格:不可购买
  • 会员用户购买价格:999积分
  • 永久会员用户购买价格:免费推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(1)

  • Lazy宇 永久会员 2021年10月13日 下午5:48

    我懂了,第一题是 归并排序的一部分(思路),第二题应该 冒泡排序,选择排序,插入排序,(原地排序)都可以用, 这个 第三题是 插入排序的一部分(思路)。