問(wèn)題描述

問(wèn)題編號(hào)為 163，題目要求我們?cè)诮o定的閉區(qū)間 [lower, upper] 內(nèi)，找出那些在整數(shù)數(shù)組 nums 中缺失的數(shù)字區(qū)間。這就好比我們有一個(gè)完整的數(shù)字區(qū)間，但其中部分?jǐn)?shù)字被拿走了，我們需要找出那些空缺的部分。

解題思路與過(guò)程剖析

方法簽名

public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper)

這個(gè)方法接收三個(gè)參數(shù)：一個(gè)整數(shù)數(shù)組 nums，以及兩個(gè)整數(shù) lower 和 upper，它的任務(wù)是返回一個(gè)包含所有缺失區(qū)間的列表。每個(gè)缺失區(qū)間都由一個(gè)包含兩個(gè)整數(shù)的列表表示，分別是區(qū)間的起始和結(jié)束值。

初始化操作

List<List<Integer>> res = new ArrayList<>();
long pre = (long) lower - 1;

這里，我們創(chuàng)建了一個(gè) res 列表，用于存儲(chǔ)最終的結(jié)果。而 pre 變量被初始化為 lower - 1，它的作用是記錄前一個(gè)檢查過(guò)的數(shù)字，方便我們后續(xù)判斷是否存在缺失區(qū)間。使用 long 類型是為了避免可能出現(xiàn)的整數(shù)溢出問(wèn)題。

數(shù)組遍歷

for (int i = 0; i <= nums.length; i++) {
    long cur = i == nums.length ? (long) upper + 1 : nums[i];

我們通過(guò)一個(gè) for 循環(huán)來(lái)遍歷數(shù)組 nums。需要注意的是，循環(huán)條件是 i <= nums.length，這意味著我們會(huì)多進(jìn)行一次迭代。在最后一次迭代時(shí)，cur 會(huì)被設(shè)為 upper + 1，這樣做是為了確保我們能檢查到區(qū)間 [lower, upper] 的最后一個(gè)數(shù)字。

檢查缺失區(qū)間

if (cur - pre > 1) {
    List<Integer> list = new ArrayList<>();
    list.add((int) pre + 1);
    list.add((int) cur - 1);
    res.add(list);
}

在每次迭代中，我們會(huì)比較 cur 和 pre 的差值。如果差值大于 1，說(shuō)明在 pre 和 cur 之間存在缺失的數(shù)字，我們就創(chuàng)建一個(gè)新的區(qū)間，起始值為 pre + 1，結(jié)束值為 cur - 1，并將這個(gè)區(qū)間添加到結(jié)果列表 res 中。

更新 pre

pre = cur;

為了確保下一次檢查的準(zhǔn)確性，我們將 pre 更新為當(dāng)前的 cur，這樣在下次迭代時(shí)，我們就能基于新的 pre 值繼續(xù)判斷是否存在缺失區(qū)間。

返回結(jié)果

return res;

最后，我們返回包含所有缺失區(qū)間的列表 res，這就是我們整個(gè)算法的最終輸出。

完整代碼

class Solution{
    publicList<List<Integer>>findMissingRanges(int[] nums,int lower,int upper){
        List<List<Integer>> res =newArrayList<>();
        long pre =(long) lower -1;
        for(int i =0; i <= nums.length; i++){
            long cur = i == nums.length ?(long) upper +1: nums[i];
            if(cur - pre >1){
                List<Integer> list =newArrayList<>();
                list.add((int) pre +1);
                list.add((int) cur -1);
                res.add(list);
            }
            pre = cur;
        }
        return res;
    }
}

復(fù)雜度分析

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

雖然原內(nèi)容中時(shí)間復(fù)雜度標(biāo)記為 O(∗)，但實(shí)際上，我們只對(duì)數(shù)組 nums 進(jìn)行了一次遍歷，因此時(shí)間復(fù)雜度為 O(n)O(n)，其中 nn 是數(shù)組 nums 的長(zhǎng)度。

空間復(fù)雜度

空間復(fù)雜度方面，除了存儲(chǔ)結(jié)果的列表 res 外，我們只使用了常數(shù)級(jí)的額外空間，所以空間復(fù)雜度為 O(m)O(m)，這里的 mm 是缺失區(qū)間的數(shù)量。

通過(guò)以上的分析，我們可以看到，這個(gè)算法巧妙地利用了一次遍歷和簡(jiǎn)單的條件判斷，高效地解決了缺失區(qū)間的查找問(wèn)題。希望大家在遇到類似的算法問(wèn)題時(shí)，也能像“東百牧碼人”一樣，通過(guò)清晰的思路和簡(jiǎn)潔的代碼來(lái)攻克難題。

以上就是Java缺失區(qū)間的查找方法的詳細(xì)內(nèi)容，更多關(guān)于Java查找缺失區(qū)間的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論