This is the third day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Leetcode -581- Shortest unordered contiguous subarray

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

Given an array of integers, nums, you need to find a contiguous subarray, and if you sort that subarray in ascending order, the entire array will be sorted in ascending order.

Find the shortest subarray and print its length.

Example 1:

Input: nums = [2,6,4,8,10,9,15] output: 5 description: you only need to sort [6, 4,8,10,9] in ascending order, then the entire table will be sorted in ascending order.Copy the code

Example 2:

Input: nums = [1,2,3,4] output: 0Copy the code

Example 3:

Input: nums = [1] Output: 0Copy the code

Tip:

Advanced: Can you design a solution with time complexity O(n)?

Related Topics

  • The stack
  • greedy
  • An array of
  • Double pointer
  • The sorting
  • Monotonous stack

👍 👎 0 597

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Sort + double pointer

  • The easiest thing to do is to sort
  • Double pointer before and after the scan to different elements
public int findUnsortedSubarray(int[] nums) {
    int[] copy = new int[nums.length];
    for (int i = 0; i < nums.length; i++){ copy[i] = nums[i]; }int i = 0, j = nums.length - 1;
    Arrays.sort(nums);
    for (; i < nums.length; i++) {
        if(copy[i] ! = nums[i]) {break; }}for (; j >= i; j--) {
        if(copy[j] ! = nums[j]) {break; }}return j-i+1;
}
Copy the code

The time complexity is O(NLGN)

Idea 2: Partition scan + double pointer

  • Running through a few use cases, the repetition element is very influential in the calculation
  • For the two intervals solved below, repartition the two boundaries respectively
  • Define two out-of-bounds numbers as the minimum and maximum elements
  • Prevents the iJ interval from having some elements that are minimum or maximum elements moving to the boundary
  • If nums[I] is smaller than nums[I], the element to the left of I should be traced back
  • If smaller than the starting element, move I to the header pointer and update min to the out-of-bounds minimum
  • Perform the reverse operation on J
  • When I equals equals j you get no interchange
  • i! =j
    • I is defined as the last left element not moved
    • J is defined as the last element on the right that is not moved
  • The number of elements that need to be moved directly is j-1 – (I +1) +1;
public int findUnsortedSubarray(int[] nums) {
    int MIN = -10005, MAX = 100005;
    //corner case
    if (nums.length == 1) {
        return 0;
    }
    int n = nums.length, i = 0, j = n - 1;
    // Find two increments starting with the start element and ending with the end element
    while (i < j && nums[i] <= nums[i + 1]) {
        i++;
    }

    while (j > i && nums[j] >= nums[j - 1]) {
        j--;
    }
    int l = i, r = j, min = nums[i], max = nums[j];
    for (int k = l; k <= r; k++) {
        if (nums[k] < min) {
            while (i >= 0 && nums[i] > nums[k]) {
                i--;
            }
            min = i >= 0 ? nums[i] : MIN;
        }
        if (nums[k] > max) {
            while(j < nums.length && nums[j] < nums[k]) { j++; } max = j < n ? nums[j] : MAX; }}return j == i ? 0 : (j - 1) - (i + 1) + 1;
}
Copy the code

Time complexity O(n)