需要排序的最短子数组

需要排序的最短子数组

问题

这个题目说的是，给你一个整数数组，你要找到一个最短的子数组，只要把它按递增排序，那么整个数组就变成递增有序。最后返回这个最短子数组的长度。注意，子数组要求是连续的。

比如说，给你的数组是 0, 2, 4, 1, 8。我们至少需要把子数组 2, 4, 1 排序，变成 1, 2, 4，才能使得整个数组有序。因此要返回这个子数组的长度 3。

代码

public class AlgoCasts {

  // Time: O(n*log(n)), Space: O(n)
  public int findUnsortedSubarrayBySorting(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int i = 0, j = nums.length - 1;
    while (i < nums.length && nums[i] == sorted[i]) ++i;
    while (j >= 0 && nums[j] == sorted[j]) --j;
    return Math.max(j - i + 1, 0);
  }

  // Time: O(n), Space: O(1)
  public int findUnsortedSubarrayTwoPass(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    int i = 0, j = n - 1;
    while (i < n-1 && nums[i] <= nums[i+1]) ++i;
    while (j > 0 && nums[j] >= nums[j-1]) --j;
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int k = i; k <= j; ++k) {
      min = Math.min(min, nums[k]);
      max = Math.max(max, nums[k]);
    }
    // expand
    while (i >= 0 && min < nums[i]) --i;
    while (j < n && max > nums[j]) ++j;
    // i+1 ~ j-1
    return Math.max(j - i - 1, 0);
  }

  // Time: O(n), Space: O(1)
  public int findUnsortedSubarrayOnePass(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    int i = 0, j = -1, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int k = 0; k < n; ++k) {
      max = Math.max(max, nums[k]);
      if (nums[k] != max) j = k;
      int p = n - 1 - k;
      min = Math.min(min, nums[p]);
      if (nums[p] != min) i = p;
    }
    return j - i + 1;
  }

}