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