資訊專欄INFORMATION COLUMN
摘要：題目解答這題用會(huì)通過很快定位到當(dāng)前數(shù)所處在哪兩個(gè)之間，從而進(jìn)行高效的比較與合并。
題目：
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:
[1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7]
Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream"s size?
解答：
這題用Maptree會(huì)通過map.lowerKey, map.higherKey很快定位到當(dāng)前數(shù)所處在哪兩個(gè)interval之間，從而進(jìn)行高效的比較與合并。
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class SummaryRanges {
TreeMap map;
/** Initialize your data structure here. */
public SummaryRanges() {
map = new TreeMap<>();
}
public void addNum(int val) {
if (map.containsKey(val)) return;
Integer l = map.lowerKey(val);
Integer h = map.higherKey(val);
if (l != null && h != null && map.get(l).end + 1 == val && val + 1 == map.get(h).start) {
map.get(l).end = map.get(h).end;
map.remove(h);
} else if (l != null && val <= map.get(l).end + 1) {
map.get(l).end = Math.max(map.get(l).end, val);
} else if (h != null && map.get(h).start - 1 == val) {
map.put(val, new Interval(val, map.get(h).end));
map.remove(h);
} else {
map.put(val, new Interval(val, val));
}
}
public List getIntervals() {
return new ArrayList(map.values());
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* List param_2 = obj.getIntervals();
*/
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65000.html
摘要：科學(xué)計(jì)算與數(shù)據(jù)可視化程序設(shè)計(jì)模塊最重要的一個(gè)特點(diǎn)就是其維數(shù)組對(duì)象即該對(duì)象是一個(gè)快速而靈活的大數(shù)據(jù)集容器。兩行及以上為二維表示數(shù)組各維度大小的元組。 科學(xué)計(jì)算與數(shù)據(jù)可視化1 @(程序設(shè)計(jì)) numpy模塊 Numpy最重要的一個(gè)特點(diǎn)就是其N維數(shù)組對(duì)象（即ndarray）該對(duì)象是一個(gè)快速而靈活的大數(shù)據(jù)集容器。 使用Numpy，開發(fā)人員可以執(zhí)行以下操作： 1、數(shù)組的算數(shù)和邏輯運(yùn)算。 2、...
摘要：而且我們可以看到他自動(dòng)幫我們安裝了，，等等需要注意的是最后會(huì)出現(xiàn)這里選擇才能把加入環(huán)境變量中，然后才能使用不然之后就得手動(dòng)配置。來安裝支持的。步驟中下載太慢了，需要個(gè)小時(shí)，還是直接在線安裝吧，先下載這個(gè)，然后這個(gè)只需要分鐘左右。 前言 最近上了幾門深度學(xué)習(xí)的公開課，還是覺得不過癮，總覺得要搞一個(gè)框架來試試。那么caffe,tensorflow,torch等等選哪一個(gè)呢？經(jīng)過一番比較我還...
閱讀 1832·2019-08-30 15:55
閱讀 1029·2019-08-26 11:57
閱讀 534·2019-08-26 11:29
閱讀 3376·2019-08-26 10:49
閱讀 1928·2019-08-23 18:40
閱讀 1835·2019-08-23 16:04
閱讀 3122·2019-08-23 11:01
閱讀 2293·2019-08-23 10:56
