Shortest Unsorted Continuous Subarray LT581
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 <=.
Idea 1. Similar to Max Chunks To Make Sorted II LT768, find the chunks and merge chunks by updating the end index, start index is the staring point of first chunk, the lengh = end index - start index.
The key point is: The array is considered sorted if the left elements are smaller or equal than the right elements, that is, the maximum of the left subarray is smaller or equal than the minimum of the right subarray.
The unsorted chunks can be found by:
a. store the minValue from right to left
b. stack in ascending order.
Time complexity: O(n)
Space complexity: O(n)
1.a
class Solution {
public int findUnsortedSubarray(int[] nums) {
int sz = nums.length;
int[] rightMin = new int[sz];
rightMin[sz-1] = nums[sz-1];
for(int i = sz-2; i >= 0; --i) {
rightMin[i] = Math.min(rightMin[i+1], nums[i]);
}
int startIndex = -1;
int endIndex = -1;
int currMax = Integer.MIN_VALUE;
for(int i = 0; i + 1 < sz; ++i) {
currMax = Math.max(currMax, nums[i]);
if(currMax > rightMin[i+1]) {
if(startIndex == -1) {
startIndex = i; // first unsorted chunk
}
else {
endIndex = -1; // new unsorted chunk, mark endIndex = -1 to merge
}
}
else if(startIndex != -1 && endIndex == -1){
endIndex = i; // if curMax <= rightMin[i+1], means nums(i+1...end) is sorted
}
}
if(startIndex == -1) {
return 0;
}
if(endIndex == -1) {
endIndex = sz - 1;
}
return endIndex - startIndex + 1;
}
}
1.b stack
class Solution {
public int findUnsortedSubarray(int[] nums) {
Deque<Integer> ascendingStack = new LinkedList<>();
int startIndex = nums.length;
int endIndex = -1;
int currMaxIndex = 0;
for(int i = 0; i < nums.length; ++i) {
if(currMaxIndex == nums.length || nums[currMaxIndex] < nums[i] ) {
currMaxIndex = i;
}
while(!ascendingStack.isEmpty() && nums[ascendingStack.peek()] > nums[i]) {
startIndex = Math.min(startIndex, ascendingStack.pop()); // unsorted chunk
endIndex = -1;
}
ascendingStack.push(currMaxIndex);
if(startIndex != nums.length && endIndex == -1) {
endIndex = i; // the end of unsorted chunk: the current index i
}
}
if(startIndex == nums.length) {
return 0; // the array is sorted
}
return endIndex - startIndex + 1;
}
}
Idea 2. The boundary of unsorted subarray is determined by the leftmost and rightmost elements not in the correct position(the sorted position). Borrow the idea from selection sort, for any pair of integeras (0 < i < j < nums.length), if num[i] > nums[j], this pair will get swapped to get the right position for the sorted array, since we only require the bounday, there is no need to sort it, just note down the index of elements which mark the boundary of the unsorted subarray. Hence, out of all pairs, the leftmost index i not at it's correct position is the left boundary, the rightmost index j is the right boundary.
Time complexity: O(n2)
Space complexity: O(1)
class Solution {
public int findUnsortedSubarray(int[] nums) {
int startIndex = nums.length;
int endIndex = -1;
for(int i = 0; i < nums.length; ++i) {
for(int j = i; j < nums.length; ++j) {
if(nums[i] > nums[j]) {
startIndex = Math.min(startIndex, i);
endIndex = Math.max(endIndex, j);
}
}
}
if(startIndex == nums.length) {
return 0;
}
return endIndex - startIndex + 1;
}
}
Idea 3. Comparing with the correct position in the sorted array, mark down the leftmost index and rightmost index different from the sorted position.
Time complexity: O(nlogn)
Space complexity: O(n)
class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] numsSorted = Arrays.copyOf(nums, nums.length);
Arrays.sort(numsSorted);
int startIndex = nums.length;
int endIndex = -1;
for(int i = 0; i < nums.length; ++i) {
if(nums[i] != numsSorted[i]) {
startIndex = Math.min(startIndex, i);
endIndex = Math.max(endIndex, i);
}
}
if(startIndex == nums.length) {
return 0;
}
return endIndex - startIndex + 1;
}
}
Idea 4. The correct position of the minimum element in the unsorted subarray determins the left boundary, the correct position of the maximum element in the unsorted subarray determins the right boundary. Two steps: 1. Find the unsorted subarray 2. find the minimum and maximum
a. stack in ascending order for min, in descending order for maxmum
While traversing over the nums array starting from the begining, pushing elements over the stack if in asecending order, otherwise in a falling slope(unsorted subarray), an element nums[j] smaller than the element on the top of the stack, poping elements in the stack until the elemnts on the top is equal or smaller than nums[j], the last poped element is the correct position for nums[j]. For all the nums[j] not in correct position, the minmum of the correct positions determins the left boundary.
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public int findUnsortedSubarray(int[] nums) {
Deque<Integer> indexStack = new LinkedList<>();
int startIndex = nums.length;
int endIndex = -1;
for(int i = 0; i < nums.length; ++i) {
while(!indexStack.isEmpty() && nums[indexStack.peek()] > nums[i]) {
startIndex = Math.min(startIndex, indexStack.pop());
}
indexStack.push(i);
}
for(int i = nums.length-1; i >= 0; --i) {
while(!indexStack.isEmpty() && nums[i] > nums[indexStack.peek()]) {
endIndex = Math.max(endIndex, indexStack.pop());
}
indexStack.push(i);
}
if(startIndex == nums.length) {
return 0;
}
return endIndex - startIndex + 1;
}
}
b. without extra space, rising slope starting from the begining, falling slope staring from the end
Time complexity: O(n)
Space complexity: O(1)
C1 class Solution {
public int findUnsortedSubarray(int[] nums) {
int startIndex = 0;
while(startIndex+1 < nums.length && nums[startIndex] <= nums[startIndex+1]) {
++startIndex;
}
if(startIndex == nums.length-1) {
return 0;
}
int minItem = nums[startIndex+1];
for(int i = startIndex+1; i < nums.length; ++i) {
minItem = Math.min(minItem, nums[i]);
}
// nums[0..startIndex] is sorted,
// the correct position is the index of the first element bigger than minItem
// from 0 to startIndex (left to right)
for(int i = 0; i <= startIndex; ++i) {
if(nums[i] > minItem) {
startIndex = i;
break;
}
}
int endIndex = nums.length-1;
while(endIndex-1 >= 0 && nums[endIndex-1] <= nums[endIndex]) {
--endIndex;
}
int maxItem = nums[endIndex-1];
for(int i = endIndex-1; i >= 0; --i) {
maxItem = Math.max(maxItem, nums[i]);
}
// nums[endIndex, nums.length-1] is sorted
// the correct position of the index of the first element smaller than maxItem
// from nums.length-1 to endIndex (right to left)
for(int i = nums.length-1; i>= endIndex; --i) {
if(nums[i] < maxItem) {
endIndex = i;
break;
}
}
return endIndex - startIndex + 1;
}
}
Find the first unsorted subarray and the minimum element can be combine in one loop to make code more concise.
class Solution {
public int findUnsortedSubarray(int[] nums) {
int minItem = Integer.MAX_VALUE;
boolean isSorted = true;
for(int i = 1; i < nums.length; ++i){
if(nums[i-1] > nums[i]) {
isSorted = false;
}
if(!isSorted) {
minItem = Math.min(minItem, nums[i]);
}
}
if(isSorted) {
return 0;
}
int startIndex = 0;
for(; startIndex < nums.length; ++startIndex) {
if(nums[startIndex] > minItem) {
break;
}
}
int maxItem = Integer.MIN_VALUE;
isSorted = true;
for(int i = nums.length-2; i >= 0; --i) {
if(nums[i] > nums[i+1]) {
isSorted = false;
}
if(!isSorted) {
maxItem = Math.max(maxItem, nums[i]);
}
}
int endIndex = nums.length-1;
for(;endIndex >= 0; --endIndex) {
if(nums[endIndex] < maxItem) {
break;
}
}
return endIndex - startIndex + 1;
}
}
最新文章
- js瀑布流
- 74 使用BitSet输出数组中的重复元素
- 对socket的一点理解笔记
- 百度地图-marker拖拉，右键菜单
- Hibernate3回顾-3-Session管理
- C语言中结构体的初始化
- git研究2
- struts2 MessageStoreInterceptor 拦截器的使用
- 反射API
- [模拟赛] T3 最优序列
- git对远程分支和tag的操作
- Laravel5多图上传和Laravel5单图上传的功能实现
- gitbook 入门教程之使用 gitbook.com 在线开发电子书
- zw-clay字王胶泥体系列
- HDU 3594.Cactus 仙人掌图
- JavaScript高级程序设计学习(四)之引用类型
- Linux 第八周实验 进程的切换和系统的一般执行过程
- Redis的优势和特点
- T-SQL语句4
- day15(mysql 的多表查询，事务)