今天和大家聊的问题叫做 将数据流变为多个不相交区间，我们先来看题面：https://leetcode-cn.com/problems/top-k-frequent-elements/
Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.Implement the SummaryRanges class:
- SummaryRanges() Initializes the object with an empty stream.
- void addNum(int val) Adds the integer val to the stream.
- int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi].
给定一个非负整数的数据流输入 a1，a2，…，an，…，将到目前为止看到的数字总结为不相交的区间列表。
示例
例如，假设数据流中的整数为 1，3，7，2，6，…，每次的总结为： [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7] 进阶： 如果有很多合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?
解题
使用有序的哈希集合方法，来对整个数组进行排序+去重。具体的思路，只需要在纸上模拟一下求 [1, 2, 3, 6, 7] 区间的过程就好了。
class SummaryRanges { private Set<Integer> set; public SummaryRanges() { set = new TreeSet<>(); } public void addNum(int val) { set.add(val); } public int[][] getIntervals() { List<int[]> ret = new ArrayList<>(); Iterator<Integer> iterator = set.iterator(); // 逐个检查集合中相邻的两个元素 int begin = iterator.next(), end = begin; while (iterator.hasNext()) { int t = iterator.next(); // 通过比较下一个元素和当前 end 之差是不是1，看看是否需要开始新的区间 if (t != end + 1) { // 如果需要更新的话，就先把当前区间放到返回值中，然后再重新开始新的区间 ret.add(new int[]{begin, end}); begin = t; end = begin; } else { // 否则的话，就更新当前区间的 end end = t; } } // 最后需要把剩余的区间放到返回值中 ret.add(new int[]{begin, end}); return ret.toArray(new int[ret.size()][]); } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
