LeetCode·581.最短无序连续子数组·双指针

链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solution/by-xun-ge-v-86rd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路

• 解法一：排序法

因为题目需要我们找到最短无序连续子数组，最终目的是让整个数组有序，那么我们可以先将数组拷贝一份进行排序，然后使用两个指针 i 和 j 分别找到左右两端第一个不同的地方，那么 [i,j] 这一区间即是答案、即为最短无序连续子数组

• 解法二：双指针双向扫描

与解法一大体思路是一样的。我们要得到的是一个升序数组，那么我们定义两个指针 i 和 j ，分别对数组进行双向扫描。

• 对于左指针 i 而言，我们寻找最后一个降序地方；
• 对于右指针 j 而言， 我们寻找第一个降序的地方；

将第一个降序的地方和最后一个降序的地方也就是区间【j ， i】，进行升序处理，是不是就得到了整体数组为升序了。

代码 

• 解法一：排序法

• int cmp(const void * a, const void * b)//升序子函数
  {
      return *(int *)a - *(int *)b;
  }
  /*
  *int findUnsortedSubarray(int* nums, int numsSize)
  int findUnsortedSubarray：寻找不符合区间
  int* nums：数组
  int numsSize：数组长度
  返回值：不符合区间长度
  */
  int findUnsortedSubarray(int* nums, int numsSize)
  {
      int * ans = malloc(sizeof(int) * numsSize);
      memcpy(ans, nums, sizeof(int) * numsSize);
      qsort(ans, numsSize, sizeof(int), cmp);//初始化变量
      int i, j;
      int n = -1, m = -1; 
      for(i = 0; i < numsSize; i++)//判断左边第一个不同点
      {
          if(ans[i] != nums[i])
          {
              n = i;
              break;
          }
      }
      for(j = numsSize-1; j >= 0; j--)//判断右边第一个不同点
      {
          if(ans[j] != nums[j])
          {
              m = j;
              break;
          }
      }
      return n == -1 ? 0 : m - n + 1; 
  }
  
  作者：xun-ge-v
  链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solution/by-xun-ge-v-86rd/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• 解法二：双指针双向扫描

/*
*int findUnsortedSubarray(int* nums, int numsSize)
int findUnsortedSubarray：寻找不符合区间
int* nums：数组
int numsSize：数组长度
返回值：不符合区间长度
*/
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++) {//双向扫描
        if (maxn > nums[i]) {寻找最后一个降序地方
            right = i;
        } else {
            maxn = nums[i];
        }
        if (minn < nums[n - i - 1]) {寻找第一个降序的地方
            left = n - i - 1;
        } else {
            minn = nums[n - i - 1];
        }
    }
    return right == -1 ? 0 : right - left + 1;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solution/by-xun-ge-v-86rd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

时间空间复杂度