16.16 部分排序

面试题 16.16. 部分排序

难度 中等

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：

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

输出： [3,9]

提示：

• 0 <= len(array) <= 1000000

Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence).

Return [m,n]. If there are no such m and n (e.g. the array is already sorted), return [-1, -1].

思路——双指针

本质

• 寻找序列中的 逆序对
• 而且，是找间隔最大的 逆序对
• 定位右侧 index：找到 最右侧 的逆序对，从左向右扫描，如果元素值变小了就是逆序对
  • 从左向右扫描，记录 元素最大值
  • 如果发现当前值 < 最大值，那么就是逆序对，记录它的 index
  • 否则，更新当前最大值到更大的值
    • 不要加上 = ，因为这会把相同的值算进最终区间内，区间就不是最小的了
• 定位左侧 index：找 最左侧 的逆序对，从右向左扫描，如果元素值变大了就是逆序对
• 返回 int[] = {左index, 右index}

实现

// 返回 目标区间 开头索引 结尾索引 组成的int数组

public static int[] subSort(int[] array) {

if (array.length == 0) return new int[]{-1, -1};

// 从左往右

int max = array[0];

int rightIndex = -1;

for (int i = 1; i < array.length; i++) {

if (array[i] < max)

rightIndex = i;

else

max = array[i];

}

int min = array[array.length - 1];

int leftIndex = -1;

for (int i = array.length - 2; i >= 0; i--) {

if (array[i] > min)

leftIndex = i;

else

min = array[i];

}

return new int[]{leftIndex, rightIndex};

}

时间复杂度 O(n)