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

LeetCode题练习与总结：最短无序连续子数组--581

article 2025/1/27 7:44:03

一、题目描述

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

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

示例 1：

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

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

提示：

1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5

二、解题思路

首先复制原数组，并对复制后的数组进行排序。
然后分别从数组的两端开始比较原数组与排序后的数组。
找到第一个不同的元素位置，即为需要排序的子数组的起始位置。
找到最后一个不同的元素位置，即为需要排序的子数组的结束位置。
计算这两个位置之间的距离，即为需要排序的最短子数组的长度。

三、具体代码

import java.util.Arrays;

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        // 复制原数组并进行排序
        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);

        // 初始化子数组的起始和结束位置
        int start = 0, end = nums.length - 1;

        // 从两端开始比较原数组与排序后的数组
        while (start < nums.length && nums[start] == sortedNums[start]) {
            start++;
        }
        while (end > start && nums[end] == sortedNums[end]) {
            end--;
        }

        // 计算需要排序的子数组的长度
        return end - start + 1;
    }
}

这段代码首先复制了原数组并进行排序，然后从数组的两端开始比较，直到找到第一个和最后一个不同的元素，最后计算这两个位置之间的距离，即为需要排序的最短子数组的长度。如果整个数组已经是有序的，那么返回的长度将是0。

四、时间复杂度和空间复杂度

1. 时间复杂度

复制原数组：这个操作的时间复杂度是 O(n)，其中 n 是数组的长度。
对数组进行排序：使用的是 Arrays.sort() 方法，该方法在大多数情况下使用的是双轴快速排序，其平均时间复杂度是 O(n log n)。
比较原数组与排序后的数组：最坏情况下需要遍历整个数组，因此时间复杂度是 O(n)。

综上所述，总的时间复杂度是 O(n) + O(n log n) + O(n)，简化后是 O(n log n)，因为排序操作通常是最大的时间开销。

2. 空间复杂度

复制原数组：这个操作的空间复杂度是 O(n)，因为需要额外的空间来存储一个与原数组大小相同的数组。

因此，总的空间复杂度是 O(n)。

五、总结知识点

数组操作：
- 使用 clone() 方法来复制一个数组。这是一个浅拷贝，适用于基本数据类型。
- 使用 Arrays.sort() 方法对数组进行排序。这个方法内部使用的是双轴快速排序算法。
循环结构：
- 使用 while 循环来遍历数组元素，以找到需要排序的子数组的起始和结束位置。
数组索引与边界条件：
- 使用数组索引来访问数组元素。
- 使用边界条件来防止数组越界。例如，start < nums.length 和 end > start。
逻辑判断：
- 使用 == 运算符来比较数组元素是否相等。
- 使用 && 运算符来进行逻辑与运算，确保在满足特定条件时才执行循环体中的代码。
算法逻辑：
- 通过比较原数组与排序后的数组，确定需要排序的子数组的边界。
- 计算子数组长度的逻辑：end - start + 1。
方法定义与返回值：
- 定义了一个 findUnsortedSubarray 方法，它接受一个整数数组作为参数，并返回一个整数，表示需要排序的子数组的长度。
Java基础语法：
- 类定义（class 关键字）。
- 方法定义（public 访问修饰符，返回类型，方法名，参数列表）。
- 变量声明与初始化（int start = 0, end = nums.length - 1;）。