ShortestUnsortedContinuousSubarray [source code]
public class ShortestUnsortedContinuousSubarray {
static
/******************************************************************************/
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int head = 0, tail = nums.length - 1;
if (nums.length <= 1) return 0;
for (head = 1; head < nums.length; head++) {
if (nums[head - 1] > nums[head]) break;
}
for (tail = nums.length - 2; tail >= 0; tail--) {
if (nums[tail] > nums[tail + 1]) break;
}
if (head - tail > 1 || head == nums.length || tail < 0) return 0;
head--;
tail++;
if (head > tail) {
int tmp = head;
head = tail;
tail = tmp;
}
int[] peaks = getMinMax(nums, head, tail);
int min = peaks[0], max = peaks[1];
int start = binarySearch(nums, min, 0, head - 1, false);
int end = binarySearch(nums, max, tail + 1, nums.length - 1, true) - 1;
return end - start + 1;
}
public int binarySearch(int[] nums, int val, int lo, int hi, boolean isTail) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == val) return mid + (isTail ? 0 : 1);
else if (nums[mid] < val) lo = mid + 1;
else hi = mid - 1;
}
return lo;
}
public int[] getMinMax(int[] nums, int lo, int hi) {
int min = nums[lo], max = nums[lo];
for (int i = lo; i <= hi; i++) {
if (nums[i] < min) min = nums[i];
if (nums[i] > max) max = nums[i];
}
return new int[]{min, max};
}
}
/******************************************************************************/
public static void main(String[] args) {
ShortestUnsortedContinuousSubarray.Solution tester = new ShortestUnsortedContinuousSubarray.Solution();
int[][] inputs = {
{2, 6, 4, 8, 10, 9, 15}, {5},
{1,2,3,4,5,2}, {4},
{1,2,3,4}, {0},
{2,3,3,2,4}, {3},
{1,3,2,3,3}, {2},
{1,3,5,4,2}, {4},
{5,4,3,2,1}, {5},
{0,5,10,5,0,5,10}, {5},
{1,2},{0},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println(Printer.seperator());
int[] nums = inputs[2 * i];
int expected = inputs[1 + 2 * i][0];
int output = tester.findUnsortedSubarray(nums);
Printer.openColor("magenta");
System.out.print(Printer.array(nums));
Printer.closeColor();
System.out.print(" -> " + output);
Printer.openColor(output == expected ? "green" : "red");
System.out.println(", expected: " + expected);
Printer.closeColor();
}
}
}
这个题好像脑子里如果有一个三角形的visual, 会帮助理解不少;
这题DP好像不好做, 因为找不到一个合适的DP value: 一般DP value都是跟比如, end这个entry挂钩, 但是这里的不行, 因为这里这个subarray的位置是不知道的, 未必会和end挂钩;
吭哧吭哧好不容易做完了, 这个题目细节各种变量上的更新处理太麻烦了. 最后的速度是24ms (89%), 速度应该是O(N);
面试要是碰到这个题目真的跪了, 一个小时之内肯定不能AC, 自己在家写的时候还多亏了一个case一个case的找自己的逻辑漏洞才写完了, 要是面试基本懵逼了;
另外变量更新的时候, 一定要记清楚(尤其是针对某一个具体的例子)自己设置的变量代表的具体是什么意思, 指的是哪一个. 我这里的head and tail刚开始就是因为没有理解好这两个指针本身真正的意思, 所以导致搜索范围不对;
这个是editorial1的暴力解, 速度是N^3, 虽然很慢, 但是代码写法上面很多地方还是可以学习的:
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int res = nums.length;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j <= nums.length; j++) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, prev = Integer.MIN_VALUE;
for (int k = i; k < j; k++) {
min = Math.min(min, nums[k]);
max = Math.max(max, nums[k]);
}
if ((i > 0 && nums[i - 1] > min) || (j < nums.length && nums[j] < max))
continue;
int k = 0;
while (k < i && prev <= nums[k]) {
prev = nums[k];
k++;
}
if (k != i)
continue;
k = j;
while (k < nums.length && prev <= nums[k]) {
prev = nums[k];
k++;
}
if (k == nums.length) {
res = Math.min(res, j - i);
}
}
}
return res;
}
}
主要要学习的就是他这里的遍历的方法: 找好你的iterator是什么; 这里他用的是i和j, 分别是搜索的subarray的起点和终点;
这个是editorial2:
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int l = nums.length, r = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
r = Math.max(r, j);
l = Math.min(l, i);
}
}
}
return r - l < 0 ? 0 : r - l + 1;
}
}
虽然最后的速度不好(O(N^2)), 但是思路还是很清晰的, 就是一个遍历每一个entry, 然后向右找自己的correct position. 记录所有entry的最左最右position的最值就行了; 最后的代码也很简短;
这个解法看起来简单, 其实背后的原理还是很巧妙的, 这个做法的本质就是所有的out of order的pair, 然后所有pair的最左边缘就是我们要找的SUCS的左端点, 类似的, 所有pair的最右边就是SUCS的最右. 感觉这个论断是要证明一下的;
好像也不是特别难证明: 首先, 这两个端点中间的,肯定是unsorted, 这个很自然的, 因为是由out of order pairs决定的; 其次, 要证明是shortest: 假设有一个比它更短, 那么至少有一个out of order pair没有被涵盖, 那么这个pair的一个端点不被SUCS包括, 另外一个端点被包括; 只有SUCS会被re-sort, 那么这个pair肯定还是会保持out of order. 比如我们有一个[4,2]的pair, 2在SUCS里面, 4不在(左端点被遗漏), 那么SUCS无论怎么被sort, 4始终还是在2的左边, 那么最后得到的就不可能是overall sorted;
注意这里证明shortest的时候用not shorter更好证明, 我一开始想要用any longer won't work, 不过这个相对好像难证明一些;
editorial3:
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] snums = nums.clone();
Arrays.sort(snums);
int start = snums.length, end = 0;
for (int i = 0; i < snums.length; i++) {
if (snums[i] != nums[i]) {
start = Math.min(start, i);
end = Math.max(end, i);
}
}
return (end - start >= 0 ? end - start + 1 : 0);
}
}
这个就是用sorting做的, 很简单的一个思路; 注意这里的clone的用法(sort本身是mutating的, 所以不能直接按在nums上就sort);
另外注意他这里做到了只用一个循环走一遍就行了, 而不是两头分别走, 走到mismatch分别停止; 这个也是一个可以借鉴的技巧; 我们要找的其实就是the first and last mismatch, 那么其实就是the min and max of indices of all mismatches, 这个min and max在一个循环里写掉就容易想的多了;
editorial4:
The idea behind this approach is also based on selective sorting. We need to determine the correct position of the minimum and the maximum element in the unsorted subarray to determine the boundaries of the required unsorted subarray.
这个应该就是跟我的思路差不多了, 不过他的代码比我的短很多, 不知道是不是因为没有写subroutine的原因;
他这里用了一个Stack, 毕竟这个问题是一个锯齿形问题, 而且有一个趋势的概念在里面 , 不过针对这个问题本身, 他这里的Stack本身完成的其实就是一个线性搜索的功能.
public class Solution {
public int findUnsortedSubarray(int[] nums) {
Stack <Integer> stack = new Stack <> ();
int l = nums.length, r = 0;
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
l = Math.min(l, stack.pop());
stack.push(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
r = Math.max(r, stack.pop());
stack.push(i);
}
return r - l > 0 ? r - l + 1 : 0;
}
}
好像不是线性搜索! 他这个Stack最后做到的速度其实是O(N)的. 这个题目的思路还是从两头开始找拐点. 我的做法是直接两头看到拐点之后, 拐点中间的部分(包括拐点本身)统一找到最值, 然后两个最值在拐点以外的区域找到正确的位置就行了;
我的算法加速的原因有两点: 拐点中间的这个subarray我真正完成search for correct position的其实就两个最值; 其次, 我搜索正确位置的时候使用Binary Search.
如果是线性搜索, 拐点中间的每一个都向外搜索一次正确位置, 那么速度是可能到O(N^2)的.
但是他这里用Stack之后就不一样了;
想问题还是要结合例子来想, 就算是这里用折线的visual, 也最好要先有一个具体的例子, 然后这个visual从这个例子之上总结抽象出来;
不过这个做法最后好像是因为overhead, 速度非常差(80ms);
刚开始没有看懂这个思路到底是什么意思: 比如说从左到右的这个pass, 我们首先Stack里面存的就是左边所有的sorted的趋势, 然后从拐点开始, 每一个entry尝试从这个Stack里面pop出来尽可能深的index(or the leftmost sorted subarray), 最后实质情况就是, 真正挖的最深的就是拐点中间的最小值; 这里的push其实真正有效的push就是刚开始在sorted subarray的时候的几个push有用. 真正进入拐点以后, pop完了之后的那个push其实是没有意义的(最后能够更新的就是看谁能够在sorted subarray的index里面挖的更深), 不过如果代码上想要把这两种push区分开来太麻烦, 所以干脆就直接一起push了;
这里Stack的作用其实就类似一个在最值问题中减少操作量的作用: 如果一个index已经被挖出来了, 那么后面的index就不用考虑它了, 除非新的entry能够挖的更深, 否则就没有差别;
editorial4就是用我的两个最值的方法来做. 注意, 出现拐点的位置, 是where the SUCS MUST already started, not exactly where it started. 他这里跟我的一个不同是他给两个最值找正确位置的时候直接就是线性搜索. 想想我这个Binary Search确实也没有必要, 因为毕竟这个线性搜索只要走两个就行了; 不过看到了sorted, 不Binary Search还是有点不舒服;
这个是discussion上面一个看似简单但是实际上很聪明的解:
public int findUnsortedSubarray(int[] A) {
int n = A.length, beg = -1, end = -2, min = A[n-1], max = A[0];
for (int i=1;i<n;i++) {
max = Math.max(max, A[i]);
min = Math.min(min, A[n-1-i]);
if (A[i] < max) end = i;
if (A[n-1-i] > min) beg = n-1-i;
}
return end - beg + 1;
}
这个是comment里面的一个解释:
Awesome!
Some explanations:
endIdx = The most right element having greater elements on the left side.
begIdx = The most left element having smaller elements on the right side.
Prove it is effective:
According to the definition, we can know that all elements on the right side of endIdx do not have greater elements on the left side and all elements on the left side of the begIdx do not have greater elements on the right side. Therefore, these two parts are good and we only need to sort the elements between begIdx and endIdx.
Prove the bounds are tight:
According to the definition, the two elements at begIdx and endIdx are "illegal", so the range to be sort should at least include these two elements.
大概意思就是找到最远端的两个misplaced entry. 找到的办法就是跟两头的最值进行比较: 如果你的左边有一个比你大的, 那么你左边的最值肯定也比你大. 这个算法是典型的看起来简单但是实际上背后的原理非常巧妙的算法;
这里他还使用了一个小trick: 就是如果是整个array已经sorted的情况他这个算法是不用专门判断的: 如果整个是sorted, 那么beg和end肯定都不会被更新, 所以只要合理的初始化他们, 那么最后end - beg + 1就是0, 也就是sorted的expected answer;
Problem Description
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 <=.
Difficulty:Easy
Total Accepted:10.5K
Total Submissions:35.3K
Contributor: love_Fawn
Companies
liveramp google
Related Topics
array