题号面试题 16.16 部分排序题目内容给定一个整数数组编写一个函数找出索引m和n只要将索引区间[m,n]的元素排好序整个数组就是有序的。注意n-m尽量最小也就是说找出符合条件的最短序列。函数返回值为[m,n]若不存在这样的m和n例如整个数组是有序的请返回[-1,-1]。注0 len(array) 1000000题目中未指明是升序还是降序但经过测试题目要求的有序为升序示例输入[1,2,4,7,10,11,7,12,6,7,16,18,19]输出[3,9]解题过程与思路题目要求找到给定数组的最短子数组该子数组排序后能使得给定数组整体有序。观察一个有序数组 array对其任意切分后左边数组 array[ :i] 中的最大值一定小于等于右边数组 array[i: ] 中的最小值。因此我们可以从左到右遍历一旦从某个位置起左边数组中的最大值大于右边数组中的最小值则从这个位置开始就是子数组的起点使用一个临时数组 temp 储存子数组一旦从某个位置起子数组中的最大值小于右边数组的最小值则就是子数组的终点。使用python编写代码如下def sub_sort(array: List[int]) - List[int]: if sorted(array) array: # 如果数组已经有序则返回[-1, -1] return [-1, -1] answer [-1, -1] i 1 temp [] while i len(array): # 遍历获取子数组起点 if max(array[:i]) min(array[i:]): # 如果左边数组中的最大值大于右边数组中的最小值 answer[0] i - 1 # 记录起点由于切片的左闭右开所以需要-1 temp.append(array[i - 1]) # 记录子数组 break i 1 while i len(array): # 遍历获取子数组终点 try: if max(temp) min(array[i:]): # 如果子数组中的最大值大于右边数组中的最小值 temp.append(array[i]) # 更新子数组 else: answer[1] i - 1 # 如果子数组中的最小值小于右边数组中的最小值则记录终点由于切片的左闭右开所以需要-1 break except: answer[1] len(array) - 1 # 防止索引越界如果越界则子数组最后一个元素为原数组最后一个元素 i 1 return answer优化这是我最开始写的代码提交时通过了前 37 个验证集在第 38 个验证时提示超时。我借助 AI 获得了如下优化思路。代码中虽然有两个 while 但实际上只遍历了原数组一遍性能开销最大的是每次遍历都要获取两个数组的最大值和最小值。所以我们换个思路不要想哪段区间需要排序而是想一个元素如果不在它该在的位置它有什么特征对于一个有序数组任意一个元素 a array[i] 都有a 左边的元素都小于等于 aa 右边的元素都大于等于 a 。因此如果一个元素 a 左边的最大值大于 a 则说明这个元素是错位的同样如果一个元素 a 右边的最小值小于 a 则说明这个元素是错位的。因此我们只需要找到最两边的错位元素即可获取整个序列。同时我们可以优化获取最大值和最小值的方式在从左往右遍历的时候可以通过比较的方式来获取左边的最大值同理在从右往左遍历的时候也可以通过类似的方式获取到右边的最小值。使用双指针则一次遍历即可优化代码如下def sub_sort(array: List[int]) - List[int]: if not array: # 如果数组为空直接返回 return [-1, -1] answer [-1, -1] i 0 # 左指针 j len(array) - 1 # 右指针 left_max array[0] # 左边最大值 right_min array[-1] # 右边最小值 while i len(array): # 遍历整个数组 left_max max(left_max, array[i]) # 更新左边最大值 right_min min(right_min, array[j]) # 更新右边最小值 if array[i] left_max: # 如果一个元素 a 左边的最大值大于 a 则说明这个元素是错位的 answer[1] i # 更新元素位置 if array[j] right_min: # 如果一个元素 a 右边的最小值小于 a 则说明这个元素是错位的 answer[0] j # 更新元素位置 j - 1 i 1 # 更新指针 return answer整个逻辑稍微有点绕举例说明一下以[1, 3, 7, 5, 6, 9, 11]为例此处只说明从左到右遍历的逻辑从右到左类似。初始 i 0left_max 1遍历过程如下从左到右遍历 i 0, left_max 1, array[i] 1 i 1, left_max 3, array[i] 3 i 2, left_max 7, array[i] 7 i 3, left_max 7, array[i] 5, 此时array[i]小于left_max, 更新answer[1] 3 i 4, left_max 7, array[i] 6, 此时array[i]小于left_max, 更新answer[1] 4 i 5, left_max 9, array[i] 9 i 6, left_max 11, array[i] 11遍历结束 从右到左遍历 同上最终输出[2,4]