Leetcode · 581. shortest unordered continuous subarray · double pointer

link ：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solution/by-xun-ge-v-86rd/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source . 

subject

 

Example

 

Ideas

Their thinking

• Solution 1 ： Sequencing

Because the problem requires us to find the shortest unordered continuous subarray , The ultimate goal is to make the entire array orderly , Then we can first copy the array and sort it , Then use two pointers i and j Find the first difference between the left and right ends , that [i,j] This interval is the answer 、 That is, the shortest unordered continuous subarray

• Solution 2 ： Double pointer bidirectional scanning

The general idea of solution is the same . What we want is an ascending array , Then we define two pointers i and j , Scan the array in both directions .

• For the left pointer i for , We look for the last place in descending order ;
• For the right pointer j for , We look for the first place in descending order ;

The first place in descending order and the last place in descending order are intervals 【j , i】, Perform ascending processing , Does it mean that the whole array is in ascending order .

Code  

• Solution 1 ： Sequencing

• int cmp(const void * a, const void * b)// Ascending subfunction 
  {
      return *(int *)a - *(int *)b;
  }
  /*
  *int findUnsortedSubarray(int* nums, int numsSize)
  int findUnsortedSubarray： Find the non-conforming interval 
  int* nums： Array 
  int numsSize： The length of the array 
   Return value ： It does not conform to the interval length 
  */
  int findUnsortedSubarray(int* nums, int numsSize)
  {
      int * ans = malloc(sizeof(int) * numsSize);
      memcpy(ans, nums, sizeof(int) * numsSize);
      qsort(ans, numsSize, sizeof(int), cmp);// Initialize variable 
      int i, j;
      int n = -1, m = -1; 
      for(i = 0; i < numsSize; i++)// Judge the first difference on the left 
      {
          if(ans[i] != nums[i])
          {
              n = i;
              break;
          }
      }
      for(j = numsSize-1; j >= 0; j--)// Judge the first difference on the right 
      {
          if(ans[j] != nums[j])
          {
              m = j;
              break;
          }
      }
      return n == -1 ? 0 : m - n + 1; 
  }
  
   author ：xun-ge-v
   link ：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solution/by-xun-ge-v-86rd/
   source ： Power button （LeetCode）
   The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

• Solution 2 ： Double pointer bidirectional scanning

/*
*int findUnsortedSubarray(int* nums, int numsSize)
int findUnsortedSubarray： Find the non-conforming interval 
int* nums： Array 
int numsSize： The length of the array 
 Return value ： It does not conform to the interval length 
*/
int findUnsortedSubarray(int* nums, int numsSize) {
    int n = numsSize;
    int maxn = INT_MIN, right = -1;
    int minn = INT_MAX, left = -1;
    for (int i = 0; i < n; i++) {// Bidirectional scanning 
        if (maxn > nums[i]) { Find the last place in descending order 
            right = i;
        } else {
            maxn = nums[i];
        }
        if (minn < nums[n - i - 1]) { Find the first place in descending order 
            left = n - i - 1;
        } else {
            minn = nums[n - i - 1];
        }
    }
    return right == -1 ? 0 : right - left + 1;
}

 author ：xun-ge-v
 link ：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solution/by-xun-ge-v-86rd/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

 

Time and space complexity