Leetcode刷题java之581. 最短无序连续子数组

╰半橙微兮° 2023-07-03 15:27 30阅读 0赞

执行结果：

通过

显示详情

执行用时 :10 ms, 在所有 Java 提交中击败了56.13% 的用户

内存消耗 :39.7 MB, 在所有 Java 提交中击败了61.42%的用户

题目：

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

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: \[2, 6, 4, 8, 10, 9, 15\]  
输出: 5  
解释: 你只需要对 \[6, 4, 8, 10, 9\] 进行升序排序，那么整个表都会变为升序排序。

说明 :

输入的数组长度范围在 \[1, 10,000\]。  
输入的数组可能包含重复元素 ，所以升序的意思是<=。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

克隆一个，并排序，与原数组进行比较，找到不同的最小和最大索引

代码：

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);
        }
    }

另一种：

public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int[] snums = nums.clone();
            Arrays.sort(snums);
            int left=0;
            int right=nums.length-1;
            while(left<nums.length)
            {
                if(nums[left]!=snums[left])
                {
                    break;
                }
                left++;
            }        
            while(right>=0)
            {
                if(nums[right]!=snums[right])
                {
                    break;
                }
                right--;
            }
            return (right - left >= 0 ? right - left + 1 : 0);
        }
    }