一、題目描述

給你一個(gè)整數(shù)數(shù)組?nums?，你需要找出一個(gè)?連續(xù)子數(shù)組?，如果對(duì)這個(gè)子數(shù)組進(jìn)行升序排序，那么整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判颉?/p>

請(qǐng)你找出符合題意的?最短?子數(shù)組，并輸出它的長(zhǎng)度。

示例 1：

輸入：nums = [2,6,4,8,10,9,15]
輸出：5
解釋：你只需要對(duì) [6, 4, 8, 10, 9] 進(jìn)行升序排序，那么整個(gè)表都會(huì)變?yōu)樯蚺判颉?

示例 2：

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

示例 3：

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

提示：

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

二、解題思路

1. 首先復(fù)制原數(shù)組，并對(duì)復(fù)制后的數(shù)組進(jìn)行排序。
2. 然后分別從數(shù)組的兩端開(kāi)始比較原數(shù)組與排序后的數(shù)組。
3. 找到第一個(gè)不同的元素位置，即為需要排序的子數(shù)組的起始位置。
4. 找到最后一個(gè)不同的元素位置，即為需要排序的子數(shù)組的結(jié)束位置。
5. 計(jì)算這兩個(gè)位置之間的距離，即為需要排序的最短子數(shù)組的長(zhǎng)度。

三、具體代碼

import java.util.Arrays;class Solution {public int findUnsortedSubarray(int[] nums) {// 復(fù)制原數(shù)組并進(jìn)行排序int[] sortedNums = nums.clone();Arrays.sort(sortedNums);// 初始化子數(shù)組的起始和結(jié)束位置int start = 0, end = nums.length - 1;// 從兩端開(kāi)始比較原數(shù)組與排序后的數(shù)組while (start < nums.length && nums[start] == sortedNums[start]) {start++;}while (end > start && nums[end] == sortedNums[end]) {end--;}// 計(jì)算需要排序的子數(shù)組的長(zhǎng)度return end - start + 1;}
}

這段代碼首先復(fù)制了原數(shù)組并進(jìn)行排序，然后從數(shù)組的兩端開(kāi)始比較，直到找到第一個(gè)和最后一個(gè)不同的元素，最后計(jì)算這兩個(gè)位置之間的距離，即為需要排序的最短子數(shù)組的長(zhǎng)度。如果整個(gè)數(shù)組已經(jīng)是有序的，那么返回的長(zhǎng)度將是0。

四、時(shí)間復(fù)雜度和空間復(fù)雜度

1. 時(shí)間復(fù)雜度

• 復(fù)制原數(shù)組：這個(gè)操作的時(shí)間復(fù)雜度是 O(n)，其中 n 是數(shù)組的長(zhǎng)度。
• 對(duì)數(shù)組進(jìn)行排序：使用的是?Arrays.sort()?方法，該方法在大多數(shù)情況下使用的是雙軸快速排序，其平均時(shí)間復(fù)雜度是 O(n log n)。
• 比較原數(shù)組與排序后的數(shù)組：最壞情況下需要遍歷整個(gè)數(shù)組，因此時(shí)間復(fù)雜度是 O(n)。

綜上所述，總的時(shí)間復(fù)雜度是 O(n) + O(n log n) + O(n)，簡(jiǎn)化后是 O(n log n)，因?yàn)榕判虿僮魍ǔＪ亲畲蟮臅r(shí)間開(kāi)銷(xiāo)。

2. 空間復(fù)雜度

• 復(fù)制原數(shù)組：這個(gè)操作的空間復(fù)雜度是 O(n)，因?yàn)樾枰~外的空間來(lái)存儲(chǔ)一個(gè)與原數(shù)組大小相同的數(shù)組。

因此，總的空間復(fù)雜度是 O(n)。

五、總結(jié)知識(shí)點(diǎn)

• 數(shù)組操作：

  • 使用?clone()?方法來(lái)復(fù)制一個(gè)數(shù)組。這是一個(gè)淺拷貝，適用于基本數(shù)據(jù)類(lèi)型。
  • 使用?Arrays.sort()?方法對(duì)數(shù)組進(jìn)行排序。這個(gè)方法內(nèi)部使用的是雙軸快速排序算法。

• 循環(huán)結(jié)構(gòu)：

  • 使用?while?循環(huán)來(lái)遍歷數(shù)組元素，以找到需要排序的子數(shù)組的起始和結(jié)束位置。

• 數(shù)組索引與邊界條件：

  • 使用數(shù)組索引來(lái)訪問(wèn)數(shù)組元素。
  • 使用邊界條件來(lái)防止數(shù)組越界。例如，start < nums.length?和?end > start。

• 邏輯判斷：

  • 使用?==?運(yùn)算符來(lái)比較數(shù)組元素是否相等。
  • 使用?&&?運(yùn)算符來(lái)進(jìn)行邏輯與運(yùn)算，確保在滿足特定條件時(shí)才執(zhí)行循環(huán)體中的代碼。

• 算法邏輯：

  • 通過(guò)比較原數(shù)組與排序后的數(shù)組，確定需要排序的子數(shù)組的邊界。
  • 計(jì)算子數(shù)組長(zhǎng)度的邏輯：end - start + 1。

• 方法定義與返回值：

  • 定義了一個(gè)?findUnsortedSubarray?方法，它接受一個(gè)整數(shù)數(shù)組作為參數(shù)，并返回一個(gè)整數(shù)，表示需要排序的子數(shù)組的長(zhǎng)度。

• Java基礎(chǔ)語(yǔ)法：

  • 類(lèi)定義（class?關(guān)鍵字）。
  • 方法定義（public?訪問(wèn)修飾符，返回類(lèi)型，方法名，參數(shù)列表）。
  • 變量聲明與初始化（int start = 0, end = nums.length - 1;）。

以上就是解決這個(gè)問(wèn)題的詳細(xì)步驟，希望能夠?yàn)楦魑惶峁﹩l(fā)和幫助。