【LeeCode】581. 最短无序连续子数组

LeeCode

【题目描述】

给你一个整数数组 ​​nums​​ ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

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

 ​​https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/?favorite=2cktkvj​​

【示例】

【代码】admin

思路: 要找中间的无须序列, 最简单的就是对比排序前后, begin和end的下标即可

package com.company;
import java.util.*;

// 2022-02-13
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        // 复制一下原数组
        int[] arr = Arrays.copyOf(nums, nums.length);
        // 记录下标用
        int begin = 0;
        int end = 0;
        // 原数组排序
        Arrays.sort(nums);
        // 从前往后, 新旧数组对比, 记录初始值
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == arr[i]) {
                continue;
            }else {
                begin = i;
                break;
            }
        }
        // 从后往前, 新旧数组对比, 记录结束值
        for (int i = nums.length - 1; i >= 0; i--){
            if (nums[i] == arr[i]){
                continue;
            }else {
                end = i;
                break;
            }
        }
        // 如果begin等于end, 则表示原来的数组已排序 返回0 
        int res = end - begin == 0 ? 0 : end - begin + 1;
        // System.out.println(res);
        return res;
    }
}
public class Test {
    public static void main(String[] args) {
        new Solution().findUnsortedSubarray( new int[]{2,6,4,8,10,9,15}); // 输出：5
        new Solution().findUnsortedSubarray( new int[]{1,2,3,4}); // 输出：0
        new Solution().findUnsortedSubarray( new int[]{1}); // 输出：0
    }
}

【代码】​​排序​​

package com.company;
import java.util.*;

// 2022-02-13
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if (isSorted(nums)){
            return 0;
        }
        int[] arr = new int[nums.length];
        System.arraycopy(nums, 0, arr, 0, nums.length);
        // 这里排序, 因为第一步已经判断是否是有序数组, 所以不存在越界的问题
        Arrays.sort(nums);
        int left = 0;
        while (nums[left] == arr[left]){
            left++;
        }
        int right = nums.length - 1;
        while (nums[right] == arr[right]){
            right--;
        }
        // System.out.println(right - left + 1);
        return right - left + 1;
    }

    private boolean isSorted(int[] nums) {
        for (int i = 1; i < nums.length; i++){
            if (nums[i] < nums[i - 1]){
                return false;
            }
        }
        return true;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().findUnsortedSubarray( new int[]{2,6,4,8,10,9,15}); // 输出：5
        new Solution().findUnsortedSubarray( new int[]{1,2,3,4}); // 输出：0
        new Solution().findUnsortedSubarray( new int[]{1}); // 输出：0
    }
}

扩展：leecode看到另一个比较好的几个分析

​​变形题​​

【代码】admin

package com.company;
import java.util.*;

// 2022-02-13
class Solution {
    public List<Integer> findUnsortedSubarray2(int[] nums) {
        List<Integer> list = new ArrayList<>();
     
        for (int i = 1; i < nums.length; i++){
            if (check(nums, i)){
                list.add(i);
            }
        }
        System.out.println(list);
    }
    // 分2步来: 左边小于  右边大于 
    private boolean check(int[] nums, int index) {
        // 左边小于
        for (int i = 0; i < index; i++){
            if (nums[i] > nums[index]){
                return false;
            }
        }
        // 右边大于
        for (int i = index + 1; i < nums.length; i++){
            if (nums[index] > nums[i]){
                return false;
            }
        }
        return true;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().findUnsortedSubarray2(new int[] {2,3,1,8,9,20,12}); // 输出：3,4
    }
}

【代码】​​儒雅随荷0​​

class Solution {
    public int[] findUnsortedSubarray(int[] nums) {
        int[] temp = new int[nums.length];
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            } else {
                temp[i] = -1;
            }
            if (nums[nums.length - i - 1] < min) {
                min = nums[nums.length - i - 1];
            } else {
                temp[nums.length - i - 1] = -1;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (temp[i] != -1) {
                list.add(i);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
            System.out.println(ans[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.findUnsortedSubarray(new int[] {2,3,1,8,9,20,12});
    }
}

作者：儒雅随荷0
链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solutions/920723/bian-xing-ti-zi-jie-mian-shi-by-chenjial-s4gi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。