[Leetcode] Missing Ranges 缺失區間

Gilbertat 發布于2019-08-14 12:36 / 2204人閱讀

摘要：想象一下假設數組前有一段連續的負無窮到，數組后有一段到正無窮，這樣是等價與上下界的。最后循環到停止，當下標為時，我們將當前指針指向，并判斷和數組末尾是否能構成最后一個區間。

Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

雙指針遍歷 復雜度

時間 O(N) 空間 O(1)

思路

我們用一個指針prev記錄上次range的結尾，一個指針curr記錄當前遍歷到的數字，如果curr和prev相差大于1，說明一個missing range，我們將其加入結果列表中就行了。這題主要是有幾個corner case要解決：

如何處理lower到第一個數，和最后一個數到upper的missing range？

如何區分range中只有一個數和多個數？

如何有效的得到missing range的起始和結束值，同時保證不會包含數組中的數字？

對于第一個問題，我們要做的就是在讓for循環多判斷兩次。想象一下假設數組前有一段連續的負無窮到lower-1，數組后有一段upper+1到正無窮，這樣是等價與上下界的。本來如果不考慮頭尾，那for循環本應是從1到length-1的，但是為了判斷頭，我們從0開始，將下標為0的數和lower-1比較得到第一個range。最后循環到length停止，當下標為length時，我們將當前指針指向upper+1，并判斷upper+1和數組末尾是否能構成最后一個區間。

對于第二個問題，我們只要判斷這個區間的起止是否一樣就行了

對于第三個問題，我們用prev+1和curr-1來標記這個區間的起止，因為prev和curr都是數組中的數，所以解決了每個區間的邊界問題

代碼

public class Solution {
    public List findMissingRanges(int[] nums, int lower, int upper) {
        List res = new LinkedList();
        // 初始化prev為lower-1，判斷是否存在“第一個”區間
        int prev = lower - 1, curr = 0;
        for(int i = 0 ; i <= nums.length; i++){
            // 當遍歷到length時，設置curr為upper+1，判斷是否存在“最后一個”區間
            curr = i == nums.length ? upper + 1 : nums[i];
            // 如果上一個數和當前數相差大于1，說明之間有區間
            if(curr - prev > 1){
                res.add(getRanges(prev+1, curr-1));
            }
            prev = curr;
        }
        return res;
    }
    
    private String getRanges(int from, int to){
        return from == to ? String.valueOf(from) : from + "->" + to;
    }
}

云服務器 GPU云服務器 Ranges missing LeetCode method_missing

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64590.html

[Leetcode] Summary Ranges 統計區間

摘要：雙層迭代法復雜度時間空間思路外層的循環控制每個的起點，內層的循環控制之內的遞增。每當遍歷完一個，就把它記錄到結果中，并更新下一個的起點。這里的技巧是，判斷一個數是否是在內的，只要就行了，即值之差等于下標之差。 Summary Ranges Given a sorted integer array without duplicates, return the summary of it...

Youngdze 2019-08-14 12:33 評論0 收藏0
[Leetcode] Missing Number and Missing First Positi

摘要：代碼映射法復雜度時間空間思路核心思想就是遍歷數組時，將每個元素，和以該元素為下標的元素進行置換，比如第一個元素是，就將它置換到下標為的地方，而原本下標為的地方的元素就換到第一個來。 Missing Number Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one t...

Forest10 2019-08-14 12:24 評論0 收藏0
LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個正數（First Mis

摘要：小鹿題目算法思路桶排序思想。再遍歷數組，從下標開始判斷該下標是否存放規定的數據，如果不是則該下標就是這組數據中缺失的最小正整數。桶排序還可以實現在一組數據中查找重復的數據。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿題目：First Missing Positive Give...

levius 2019-08-23 16:46 評論0 收藏0
orm2 中文文檔 3.2 模型驗證器

摘要：譯者飛龍來源模塊用于驗證數據。可用的驗證器的列表請見。驗證器也構建于中，可以這樣來訪問你可以為模型的每個屬性定義驗證器。在第一個驗證器驗證失敗之后，驗證就停止了。譯者：飛龍來源：Model Validations Enforce模塊用于驗證數據。對于使用以前的驗證器的用戶，還可以繼續使用，它們中的一部分整合到了enforce，剩余部分還沒有。推薦你開始使用orm.enforce...

zhiwei 2019-06-25 18:18 評論0 收藏0