資訊專欄INFORMATION COLUMN
摘要：想象一下假設數(shù)組前有一段連續(xù)的負無窮到，數(shù)組后有一段到正無窮，這樣是等價與上下界的。最后循環(huán)到停止，當下標為時，我們將當前指針指向，并判斷和數(shù)組末尾是否能構成最后一個區(qū)間。
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記錄當前遍歷到的數(shù)字，如果curr和prev相差大于1，說明一個missing range，我們將其加入結果列表中就行了。這題主要是有幾個corner case要解決：
如何處理lower到第一個數(shù)，和最后一個數(shù)到upper的missing range？
如何區(qū)分range中只有一個數(shù)和多個數(shù)？
如何有效的得到missing range的起始和結束值，同時保證不會包含數(shù)組中的數(shù)字？
對于第一個問題，我們要做的就是在讓for循環(huán)多判斷兩次。想象一下假設數(shù)組前有一段連續(xù)的負無窮到lower-1，數(shù)組后有一段upper+1到正無窮，這樣是等價與上下界的。本來如果不考慮頭尾，那for循環(huán)本應是從1到length-1的，但是為了判斷頭，我們從0開始，將下標為0的數(shù)和lower-1比較得到第一個range。最后循環(huán)到length停止，當下標為length時，我們將當前指針指向upper+1，并判斷upper+1和數(shù)組末尾是否能構成最后一個區(qū)間。
對于第二個問題，我們只要判斷這個區(qū)間的起止是否一樣就行了
對于第三個問題，我們用prev+1和curr-1來標記這個區(qū)間的起止，因為prev和curr都是數(shù)組中的數(shù)，所以解決了每個區(qū)間的邊界問題
代碼public class Solution {
public List findMissingRanges(int[] nums, int lower, int upper) {
List res = new LinkedList();
// 初始化prev為lower-1，判斷是否存在“第一個”區(qū)間
int prev = lower - 1, curr = 0;
for(int i = 0 ; i <= nums.length; i++){
// 當遍歷到length時，設置curr為upper+1，判斷是否存在“最后一個”區(qū)間
curr = i == nums.length ? upper + 1 : nums[i];
// 如果上一個數(shù)和當前數(shù)相差大于1，說明之間有區(qū)間
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;
}
}
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://systransis.cn/yun/64590.html
摘要：雙層迭代法復雜度時間空間思路外層的循環(huán)控制每個的起點，內層的循環(huán)控制之內的遞增。每當遍歷完一個，就把它記錄到結果中，并更新下一個的起點。這里的技巧是，判斷一個數(shù)是否是在內的，只要就行了，即值之差等于下標之差。 Summary Ranges Given a sorted integer array without duplicates, return the summary of it...
摘要：代碼映射法復雜度時間空間思路核心思想就是遍歷數(shù)組時，將每個元素，和以該元素為下標的元素進行置換，比如第一個元素是，就將它置換到下標為的地方，而原本下標為的地方的元素就換到第一個來。 Missing Number Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one t...
摘要：小鹿題目算法思路桶排序思想。再遍歷數(shù)組，從下標開始判斷該下標是否存放規(guī)定的數(shù)據(jù)，如果不是則該下標就是這組數(shù)據(jù)中缺失的最小正整數(shù)。桶排序還可以實現(xiàn)在一組數(shù)據(jù)中查找重復的數(shù)據(jù)。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿 題目：First Missing Positive Give...
摘要：譯者飛龍來源模塊用于驗證數(shù)據(jù)?？捎玫尿炞C器的列表請見。驗證器也構建于中，可以這樣來訪問你可以為模型的每個屬性定義驗證器。在第一個驗證器驗證失敗之后，驗證就停止了。 譯者：飛龍 來源：Model Validations Enforce模塊用于驗證數(shù)據(jù)。對于使用以前的驗證器的用戶，還可以繼續(xù)使用，它們中的一部分整合到了enforce，剩余部分還沒有。推薦你開始使用orm.enforce...
閱讀 3160·2021-11-22 12:01
閱讀 3779·2021-08-30 09:46
閱讀 791·2019-08-30 13:48
閱讀 3223·2019-08-29 16:43
閱讀 1671·2019-08-29 16:33
閱讀 1859·2019-08-29 13:44
閱讀 1422·2019-08-26 13:45
閱讀 2239·2019-08-26 11:44
