LeetCode 581. Shortest Unsorted Continuous Subarray (最短无序连续子数组)
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
- Then length of the input array is in range [1, 10,000].
- The input array may contain duplicates, so ascending order here means <=.
题目标签:Array
题目给了我们一个nums array, 让我们找出一个最短的无序连续子数组,当我们把这个子数组排序之后,整个array就已经是排序的了。
要找到这个子数组的范围,先要了解这个范围的beg 和 end 是如何定义的。
来看这个例子:1 5 4 5
a. 当我们找到第一个违反ascending 排序的数字 2的时候,我们不能是仅仅把beg 标记为2的前面一个数字7,而是要一直往前,找到一个合适的位置,找到在最前面位置的比2大的数字,这里是3。
b. 同样的,为了找end, 那么我们要从7的后面开始找,一直找到一个最后面位置的比7小的数字,这里是6。
这样的话,范围就是3到6 是我们要找的子数组。把3到6排序完了之后,整个array 就已经是排序的了。
这里我们可以发现,2是min, 7是max,所以我们可以分两个方向来分别寻找beg 和end。
从右到左(绿色),维护更新min 和 beg;
从左到右(红色),维护更新max 和 end。
Java Solution:
Runtime beats 89.16%
完成日期:10/15/2017
关键词:Array
关键点:分别以两个方向来找到beg 和 end
class Solution
{
public int findUnsortedSubarray(int[] nums)
{
int n = nums.length;
int beg = -1;
int end = -2; // end is -2 is because it works if the array is already in ascending order
int min = nums[n-1]; // from right to left
int max = nums[0]; // from left to right for(int i=0; i<n; i++)
{
max = Math.max(max, nums[i]);
min = Math.min(min, nums[n-1-i]); if(nums[i] < max)
end = i;
if(nums[n-1-i] > min)
beg = n-1-i;
} return end - beg + 1; // if array is already in ascending order, -2 - (-1) + 1 = 0
}
}
参考资料:
https://discuss.leetcode.com/topic/89282/java-o-n-time-o-1-space
LeetCode 题目列表 - LeetCode Questions List
最新文章
- 【原】移动web页面支持弹性滚动的3个方案
- Stack Overflow: The Architecture - 2016 Edition
- C/C++ http协议加载sessionID
- Using python to process Big Data
- MySQL的备份的一些策略和方法的总结
- NSArray和NSDictionary的混合
- UITableView详解(1)
- Haskell递归
- HUST 1376 Random intersection
- 浏览器拦截js打开新窗口
- SDWebImage源码解析
- oracle 定时 job
- Elasticsearch index fields 重命名
- 二分 poj 3273
- 调整Intellij IDEA内存
- php 原生文件下载
- 风景区的面积及道路状况分析问题 test
- Docker 启动Centos
- Bootstrap3.0 栅格系统背后的精妙魔法(Bootstrap3.0的栅格布局系统实现原理)
- linux加域退域