给定一个整数数组，你需要找出一个连续子数组，将这个子数组升序排列后整个数组都将是升序数组。
请你找出满足题设的最短的子数组。
数据范围：数组长度满足 
， 数组中的元素满足 
[编程题]最短无序连续子数组
- 排序+双指针
排完序后用双指针比对了一下原始数组，然后找出无序部分的长度
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int findUnsortedSubarray (int[] nums) {
// write code here
int n = nums.length;
int[] rawNums = Arrays.copyOfRange(nums, 0, n);
Arrays.sort(nums);
int left = 0, right = n - 1;
while(left < n && rawNums[left] == nums[left]){
left++;
}
while(right >= 0 && rawNums[right] == nums[right]){
right--;
}
return Math.max(right - left + 1, 0);
}
} 排序的时间复杂度为O(nlogn)，后面双指针的时间复杂度为O(n)，整体的时间复杂度为O(nlogn)。拷贝了原始数组，所以额外空间复杂度为O(n)。 利用单调性
如果某一个数nums[i]满足大于等于左边的最大值，小于等于右边的最小值，这个数在数组中就是不需要移动位置的。因此可以定出如下的算法流程：
- 从左往右遍历，如果nums[i]始终是nums[0:i]的最大值，就表示目前为止还是升序。如果碰到了不是最大值的情况，就记录位置，当前遇到了乱序。
- 从右往左遍历，如果nums[i]始终是nums[i:n-1]的最小值，就表示目前为止还是升序。如果碰到了不是最小值的情况，就记录位置，当前遇到了乱序。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
int leftMax = nums[0], rightMin = nums[n - 1], l = -1, r = -2;
for(int i = 1; i < n; i++){
leftMax = max(leftMax, nums[i]); // nums[0:i]的最大值
rightMin = min(rightMin, nums[n - 1 - i]); // nums[n-1-i:n-1]的最小值
if(leftMax != nums[i]){
r = i;
}
if(rightMin != nums[n - 1 - i]){
l = n - 1 - i;
}
}
return r - l + 1;
}
}; 只遍历了一遍数组，时间复杂度为O(n)。只使用了有限几个变量，空间复杂度为O(1)。
编辑于 2021-12-22 14:41:07
回复(0)
这道题，我最先想到的是单调栈解法，但正常人最先想到的应该是贪心算法，分别介绍
一： 贪心算法：
① 先拷贝数组，再对其中一个数组排序
② 从左往右比较，如果元素不同，记录第一个元素值不同的下标则为左边界
③ 从右往左遍历，如果元素不同，记录第一个元素值不同的下标则为右边界
说明：从左往右遍历和从右往左遍历只需要一次遍历即可
代码如下：
public static int findUnsortedSubarray(int[] nums) {
int[] nums2 = Arrays.copyOfRange(nums, 0, nums.length);
Arrays.sort(nums);
int left = nums.length - 1, right = 0;
boolean isLeft = true, isRight = true;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != nums2[i] && isLeft) {
left = i;
isLeft = false;
}
if (nums[nums.length - i - 1] != nums2[nums2.length - 1 - i] && isRight) {
right = nums.length - i - 1;
isRight = false;
}
}
return right <= left ? 0 : right - left + 1;
} 总结：需要排序和拷贝原数据，时间复杂度和空间复杂度略高 二： 双指针解法
① 仅需一次遍历，遍历时的同时记录全局最大值和最小值
② 从左往右遍历，找到每个比当前最大值还小的元素，则说明该元素之前存在乱序，直到遍历结束，找到的下标即为右边界
③ 同理从右往左遍历，找到每个比当前最小值还大的元素，则说明该元素右边存在乱序，直到遍历结束，确认左边界
说明：同样的从左往右和从右往左一次遍历即可
代码如下：
public static int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int l = n - 1, r = 0;
int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
// 确认右边界 r
if (nums[i] < max)
r = i;
// 更新 max
max = Math.max(max, nums[i]);
// 确认左边界 l
if (nums[n - 1 - i] > min)
l = n - 1 - i;
// 更新 min
min = Math.min(min, nums[n - 1 - i]);
}
return r > l ? r - l + 1 : 0;
} ① 将元素下标按照元素值单调递增的方式入栈
② 在构造单调栈的同时，找到逆序的元素，记录栈中逆序元素最小值，即为左边界，比如栈中元素对应值为 2,5,7 然后来个 nums[i] = 3， 则会弹出 5,7 对应的下标，记录下标最小值（即为5对应下标），这样就确认了左边界
③ 确认右边界更为简单，当构造单调栈时发现逆序，则当前的 i 即为逆序的最大下标，就为最大下标
代码如下：
public static int findUnsortedSubarray(int[] nums) {
Stack<Integer> monoStack = new Stack<>();
Stack<Integer> helper = new Stack<>();
int left = nums.length - 1, right = 0;
for (int i = 0; i < nums.length; i++) {
if (monoStack.isEmpty()) {
monoStack.push(i);
} else {
// 构建单调栈
while (!monoStack.isEmpty() && nums[monoStack.peek()] > nums[i]) {
// 找到所有比 nums[i] 要大的下标，取最小即为左边界
left = Math.min(left, monoStack.peek());
helper.push(monoStack.pop());
right = i; // 当发现乱序的时候，i 代表当前乱序的最大下标
}
monoStack.push(i);
while (!helper.isEmpty()) monoStack.push(helper.pop());
}
}
return right <= left ? 0 : right - left + 1;
} 说明：这种方法需要用到辅助栈，并且对于乱序程序较大的数组如 [100,99,......,3,2,1]，会更加频繁地出栈入栈，时间复杂度较高, 空间复杂度也较高， 稳定性较差 四： 针对三中的问题，使用优化版的单调栈：可以在弹栈后，不再使用辅助栈接收，也无需再次入栈，因为我们在弹栈时已经记录了逆序最小值（左边界），因此我们允许栈中元素缺失，但在确认右边界的时候，需要使用到全局最大值，只需要新增一个变量表示全局最大值即可
① 栈中 pop 的元素无需再次入栈，因为已经记录了最小值下标，最小值下标即为左边界
② 遍历时使用一个变量记录当前的全局最大值
③ 每个元素都与全局最大值作比较，比它小则说明左边存在乱序，于是确认右边界
优化后的代码如下：
public static int findUnsortedSubarray(int[] nums) {
Stack<Integer> monoStack = new Stack<>();
int left = nums.length - 1, right = 0, max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (!monoStack.isEmpty()) {
// 构建单调栈,找到乱序的元素最大下标 i
while (!monoStack.isEmpty() && nums[monoStack.peek()] > nums[i]) {
// 找到最小的不乱序的下标就是左边界
left = Math.min(left, monoStack.pop());
}
// 当前元素只要小于历史最大值，当前下标就是右边界
max = Math.max(max, nums[i]);
if (nums[i] < max) right = i;
}
monoStack.push(i);
}
return right <= left ? 0 : right - left + 1;
}
发表于 2024-08-16 09:50:18
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findUnsortedSubarray(vector<int>& nums) {
// write code here
vector<int> tmp;
for(int i=0; i<nums.size(); i++)
tmp.push_back(nums[i]);
sort(tmp.begin(), tmp.end());
int left =0, right = 0;
for(int i=0; i<nums.size(); i++)
{
if(nums[i] != tmp[i])
{
left = i;
break;
}
}
for(int i=nums.size()-1; i>=0; i--)
{
if(nums[i] != tmp[i])
{
right = i;
break;
}
}
if(left == 0 && right == 0)
return 0;
return right - left + 1;
}
};
发表于 2022-09-05 10:21:23
回复(0)
class Solution:
def findUnsortedSubarray(self , nums: List[int]) -> int:
# write code here
nums2 = nums[:]
nums2.sort() # 思路：复制一个数组，并且按升序排列，这个数组是满足题意后的数组；那么原数组和新数组排列不一样的子数组，就是我们要找的。
a, b = 0, 0
if nums2 == nums:
return 0
for i in range(len(nums2)):
if nums[i] != nums2[i]: # 从左往右数，当原数组和新数组的数字不一样，就是我们要找的子数组的左边界。
a = i
break
for j in range(len(nums2) - 1, -1, -1):
if nums[j] != nums2[j]: # 从右往左数，当原数组和新数组的数字不一样，就是我们要找的子数组的右边界。
b = j
break
return (b - a + 1)
def findUnsortedSubarray(self , nums: List[int]) -> int:
# write code here
nums2 = nums[:]
nums2.sort() # 思路：复制一个数组，并且按升序排列，这个数组是满足题意后的数组；那么原数组和新数组排列不一样的子数组，就是我们要找的。
a, b = 0, 0
if nums2 == nums:
return 0
for i in range(len(nums2)):
if nums[i] != nums2[i]: # 从左往右数，当原数组和新数组的数字不一样，就是我们要找的子数组的左边界。
a = i
break
for j in range(len(nums2) - 1, -1, -1):
if nums[j] != nums2[j]: # 从右往左数，当原数组和新数组的数字不一样，就是我们要找的子数组的右边界。
b = j
break
return (b - a + 1)
发表于 2022-01-03 18:30:00
回复(0)
package main
import _"fmt"
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
func findUnsortedSubarray( nums []int ) int {
n:=len(nums)
if n<2{
return 0
}
max,min:=0,n-1
ans:=[]int{0,n-1}
for l,r:=1,n-2;l<n&&r>=0;l,r=l+1,r-1{
if nums[l]<nums[max]{
ans[0]=l
}else{
max=l
}
if nums[r]>nums[min]{
ans[1]=r
}else{
min=r
}
}
if ans[0]<ans[1]{
return 0
}
return ans[0]-ans[1]+1
}
发表于 2023-03-11 17:13:00
回复(0)
单调栈
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int findUnsortedSubarray (int[] nums) {
// write code here
Stack<Integer> stack = new Stack<>();
int start = Integer.MAX_VALUE;
int end = Integer.MAX_VALUE - 1;
int curMaxNum = 0;
for(int i = 0; i < nums.length; i++){
while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){
int startTemp = stack.pop();
start = Math.min(start, startTemp);
}
// 更新最大值
curMaxNum = Math.max(curMaxNum, nums[i]);
// 如果当前不是最大值，则end 更新到当前位置
if(curMaxNum != nums[i]){
end = i;
}
stack.push(i);
}
return end - start + 1;
}
}
发表于 2022-09-08 11:37:34
回复(0)
暴力
import java.util.*;
public class Solution {
public int findUnsortedSubarray (int[] nums) {
// write code here
int start = -1;
int end = 0;
for(int i = 0 ;i<nums.length;i++){
for(int j = nums.length-1 ;j>i;j--){
if(nums[j]<=nums[i]){
end = j;//最后边的逆序对的终点
if(start==-1){
start = i;//第一个逆序对的起点
}
break;
}
}
}
if(start == -1) return 0;
return end - start + 1;
}
}
发表于 2022-03-26 13:38:21
回复(0)
问题信息
难度：
7条回答
47收藏
4435浏览
通过挑战的用户
查看代码-
2022-10-08 23:39:28
-
2022-09-17 12:29:35
-
2022-09-14 02:05:55 -
2022-09-13 12:48:52
-
2022-09-12 23:39:14
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
