Leetcode - Data Stream as Disjoint Intervals

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Given a data stream input of non-negative integers a₁, a₂, ..., a_n, ..., 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.

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();
 */

• 相关文章
• 全局相关文章