当前位置：首页 > article >正文

Java每日精进·45天挑战·Day17

article 2025/2/21 23:30:09

找出需要排序的最短子数组：一个高效的Java实现

在数据结构与算法的学习中，我们经常遇到需要优化数组或列表的问题。今天，我们要探讨的是一个有趣且实用的挑战：给定一个整数数组，找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。我们的目标是找出这个符合题意的最短子数组，并输出它的长度。

问题描述

给定一个整数数组 nums，我们需要找到一个最短的连续子数组，使得对这个子数组进行升序排序后，整个数组 nums 也将变为升序。返回这个最短子数组的长度。

示例

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

进阶思考

在解决这个问题的过程中，我们可以尝试设计一个时间复杂度为 O(n) 的解决方案，以应对大数据量的挑战。

解决方案

为了找到需要排序的最短子数组，我们可以采用以下策略：

从左到右遍历：首先，我们从左到右遍历数组，记录遍历过程中的最大值，并找到第一个破坏升序的元素。这个元素的位置将作为无序子数组的结束位置的一个候选。
从右到左遍历：接着，我们从右到左遍历数组，记录遍历过程中的最小值，并找到第一个破坏降序的元素（相对于之前记录的最大值而言）。这个元素的位置将作为无序子数组的起始位置的一个候选。
确定无序子数组：通过两次遍历，我们得到了无序子数组的起始和结束位置的候选值。根据这两个位置，我们可以确定需要排序的最短子数组。
处理特殊情况：如果在第一次遍历后没有发现破坏升序的元素，那么说明数组已经是有序的，直接返回0。

Java实现

下面是上述算法的Java实现：

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int start = n, end = 0;
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        
        // 第一次遍历找到无序子数组的结束位置和数组中的最大值
        for (int i = 0; i < n; i++) {
            if (nums[i] < max) {
                end = i;
            }
            max = Math.max(max, nums[i]);
        }
        
        // 如果没有找到无序的元素，则数组已经是有序的
        if (end == 0) {
            return 0;
        }
        
        // 第二次遍历找到无序子数组的起始位置和数组中的最小值
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] > min) {
                start = i;
            }
            min = Math.min(min, nums[i]);
        }
        
        // 返回无序子数组的长度
        return end - start + 1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        int[] nums1 = {2, 6, 4, 8, 10, 9, 15};
        System.out.println(solution.findUnsortedSubarray(nums1)); // 输出: 5
        
        int[] nums2 = {1, 2, 3, 4};
        System.out.println(solution.findUnsortedSubarray(nums2)); // 输出: 0
        
        int[] nums3 = {1};
        System.out.println(solution.findUnsortedSubarray(nums3)); // 输出: 0
    }
}