首页 > 试题广场 >

编程题二

[编程题]编程题二
  • 热度指数：501 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

1 <= nums.length <= 107

示例1

输入

[2,6,4,8,10,9,15]

输出

5

说明

你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例2

输入

[1,2,3,4]

输出

0
算法知识视频讲解
添加回答
在秋招的鸽子很漂亮头像 在秋招的鸽子很漂亮
简单好理解： 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def findUnsortedSubarray(self , nums ):
        # write code here
        num = sorted(nums)
        n_start = 0
        n_end = len(nums) - 1
        while n_start <= n_end:
            if nums[n_start] == num[n_start]:
                n_start += 1
            elif nums[n_end] == num[n_end]:
                n_end -= 1
            else:
                break
        return n_end - n_start +1
            

发表于 2022-04-10 11:15:34 回复(0)
pein531头像 pein531
比较排序前和排序后的数组，找到第一个不一致元素的索引start和最后一个不一致元素的索引end就能求得长度end - start + 1。但要注意本来就为升序的数组，这样计算出来的长度会小于0，需要特殊处理一下。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findUnsortedSubarray (int[] nums) {
        // write code here
        int[] sortedNums = Arrays.copyOfRange(nums, 0, nums.length);
        Arrays.sort(sortedNums);
        int start = 0;
        while(start < nums.length){
            if(sortedNums[start] != nums[start]) break;
            start ++;
        }
        int end = nums.length - 1;
        while(end >= 0){
            if(sortedNums[end] != nums[end]) break;
            end --;
        }
        return Math.max(end - start + 1, 0);
    }
}

编辑于 2021-09-21 10:10:42 回复(0)
不愿再收感谢信的大熊猫很有礼貌头像 不愿再收感谢信的大熊猫很有礼貌 
def findUnsortedSubarray(nums):
    n = len(nums)
    if n <= 1:
        return 0
    left, right = 0, n-1
    # 找到左端点
    while left < n-1 and nums[left] <= nums[left+1]:
        left += 1
    # 已经有序
    if left == n-1:
        return 0
    # 找到右端点
    while right > 0 and nums[right] >= nums[right-1]:
        right -= 1
    # 找到中间最小值和最大值
    min_num = float('inf')
    max_num = float('-inf')
    for i in range(left, right+1):
        min_num = min(min_num, nums[i])
        max_num = max(max_num, nums[i])
    # 扩展左端点
    while left >= 0 and nums[left] > min_num:
        left -= 1
    # 扩展右端点
    while right < n and nums[right] < max_num:
        right += 1
    return right - left - 1




编辑于 2023-03-15 15:13:32 回复(0)
nowcoder_w1头像 nowcoder_w1
排序后与原数组进行比较即可，类似双指针 
class Solution:
    def findUnsortedSubarray(self , nums ):
        sortNums = sorted(nums)
        i, j = 0, len(nums)-1
        while i<len(nums):
            if nums[i] != sortNums[i]:
                break
            i += 1
        while j>=i: # 防止重复比较
            if nums[j] != sortNums[j]:
                break
            j -= 1
        return j-i+1


编辑于 2022-04-01 17:25:06 回复(1)
牛客973466469号头像 牛客973466469号

import java.util.*;
public class Solution {
    public int findUnsortedSubarray (int[] nums) {
        
        int start=start(nums,nums.length);
        if(start==-1)
            return 0;
        int tail=start;
        int max=nums[start];
        for(int i=start;i<nums.length-1;i++){
            if(nums[i+1]<max){
                tail=i+1;
            }
            if(nums[i+1]>max){
                max=nums[i+1];
            }
}
        return tail-start+1;
    }
    
    public int start(int[] nums,int length){
        if (length <=1)
            return -1;
        for(int i=0;i<length-1;i++){
            if (nums[i]>nums[i+1])
                return i;
        }
            return -1;
    }
}

发表于 2021-09-16 10:32:55 回复(1)
牛客402943823号头像 牛客402943823号
class Solution:
    def findUnsortedSubarray(self , nums): 
        Len = len(nums)
        start, end = 0, 0
        for i in range(Len):
            if nums[i] == min(nums[i:]): continue 
            else: start = i break
        else: return 0
        for j in range(Len, 0, -1):
            if nums[j-1] == max(nums[:j]): continue
            else: end = j break
        return end - start
编辑于 2021-09-12 19:16:07 回复(0)
提交观点

问题信息

测试开发工程师 游卡 测试工程师
上传者：小小
难度：
6条回答 2259浏览

热门推荐

通过挑战的用户

相关试题

编程题二

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号