本文共 1188 字,大约阅读时间需要 3 分钟。
给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 你找到的子数组应是最短的,请输出它的长度。 示例 1: 输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。 说明 : 输入的数组长度范围在 [1, 10,000]。 输入的数组可能包含重复元素 ,所以升序的意思是<=。
思路(1)创建辅助数组,排序后和原来的数组对比,记录第一个不一样的下标和最后一个不一样的下标
时间复杂度O(nlogn) (2)更新法(不断更新min和max的值):时间复杂度O(n) 从左到右扫描(或从右到左)找局部极大值(或局部极小值),若位置放置不正确,找到其应该存在的地方 原因:从左到右找end,如果这个数比它之前最大的数要小,那么这个数字肯定要换 从右到左找start,如果这个数比它之后最小的数要大,那么这个数字肯定要换int findUnsortedSubarray(int* nums, int numsSize){ //此解法参考英文官方LeetCode上的讨论 //从左到右扫描(或从右到左)找局部极大值(或局部极小值),若位置放置不正确,找到其应该存在的地方 int n = numsSize; //赋初始开始和结束值 int start = -1; int end = -2; //结束值赋为-2是考虑在数组本身就是有序时,return也可以给出正确值 int min = nums[n - 1]; int max = nums[0]; for(int i = 0, pos = 0; i < n; i++) { pos = n - 1 - i; //找出局部极大、极小值 if(maxnums[pos]) min = nums[pos]; //如果当前值小于局部极大值,用end记录该位置,找到该max的合适位置, if(nums[i] < max) end = i; //如果当前值大于局部极小值,用start记录该位置,找到该start的合适位置 if(nums[pos] > min) start = pos; } //返回开始和结束的索引差 return end - start + 1;}
转载地址:http://grqen.baihongyu.com/