查找需要排序的最短子序列
题目:
给定一个整数数组，你需要找到一个连续的子阵。
你需要找到最短的子阵输出它的长度。
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.
//思路：将原数组序列进行排序形成新的数组，将新数组和原数组进行比较，从左边开始对比，当两个数值不一致时，返回该值位置序号
//从右边开始比较，当元素值不一样时，返回该序列号，预期值=右边的序列号-左边序列+1 ，即中间的长度就是需要进行排序的元素，输出其长度。
My
public int findUnsortedSubarray(int[] nums) {
int[] numsBySort = Arrays.copyOf(nums, nums.length);
Arrays.sort(numsBySort);
int left = 0;
int right =0;
int res = 0;
//不需要排序的情况下
if (Arrays.equals(nums, numsBySort)) {
return res;
}
for (int i = 0; i <nums.length; i++) {
if (nums[i]!=numsBySort[i]) {
if (i==nums.length-1) return nums.length;
left=i;
break;
}
}
for (int j = nums.length-1; j >0; j--) {
if (nums[j]!=numsBySort[j]) {
right=j;
break;
}
}
res=right-left+1;
return res;
}
other https://discuss.leetcode.com/topic/89282/java-o-n-time-o-1-space
publicint 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;
}
