Leetcode - Data Stream as Disjoint Intervals
https://leetcode.com/problems/data-stream-as-disjoint-intervals/
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]
Each time it adds a number, run a binary search to find a proper position to insert the element. After that run a merge interval to create a new array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | type SummaryRanges struct { intervals [][]int}/** Initialize your data structure here. */func Constructor() SummaryRanges { return SummaryRanges { intervals: [][]int{}, }}func (this *SummaryRanges) AddNum(val int) { if len(this.intervals) == 0 { this.intervals = append(this.intervals, []int{val, val}) return } left := 0 intervals := this.intervals right := len(intervals)-1 var mid int for left <= right { mid = (left+right)/2 if intervals[mid][0] <= val && intervals[mid][1] >= val { return } if intervals[mid][1] < val { left = mid + 1 } else if intervals[mid][0] > val { right = mid -1 } } firstPart := make([][]int, left) copy(firstPart, intervals[:left]) secondPart := make([][]int, len(intervals)-left) copy(secondPart, intervals[left:]) this.intervals = append(firstPart, []int{val, val}) this.intervals = append(this.intervals, secondPart...) if len(this.intervals) > 1 { this.intervals = mergeIntervals(this.intervals) }}func mergeIntervals(intervals [][]int) [][]int{ result := [][]int{} for i := 1; i < len(intervals); i++ { if intervals[i][0] - intervals[i-1][1] > 1 { result = append(result, intervals[i-1]) continue } intervals[i][0] = intervals[i-1][0] } result = append(result, intervals[len(intervals)-1]) return result}func (this *SummaryRanges) GetIntervals() [][]int { return this.intervals}/** * Your SummaryRanges object will be instantiated and called as such: * obj := Constructor(); * obj.AddNum(val); * param_2 := obj.GetIntervals(); */ |
评论 (0)
