​LeetCode刷题实战352:将数据流变为多个不相交区间

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 将数据流变为多个不相交区间,我们先来看题面:
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()][]);
    }
}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文:

LeetCode1-340题汇总,希望对你有点帮助!
LeetCode刷题实战341:扁平化嵌套列表迭代器
LeetCode刷题实战342:4的幂
LeetCode刷题实战343:整数拆分
LeetCode刷题实战344:反转字符串
LeetCode刷题实战345:反转字符串中的元音字母
LeetCode刷题实战346:数据流中的移动平均值
LeetCode刷题实战347:前 K 个高频元素
LeetCode刷题实战348:设计井字棋
LeetCode刷题实战349:两个数组的交集
LeetCode刷题实战350:两个数组的交集 II
LeetCode刷题实战351:安卓系统手势解锁
(0)

相关推荐

  • LeetCode之First Unique Character in a String

    LeetCode之First Unique Character in a String

  • LeetCode之Reverse Integer

    LeetCode之Reverse Integer

  • 【LeetCode】347. Top K Frequent Elements 前 K 个高频元素(Medium)(JAVA)

    [LeetCode]347. Top K Frequent Elements 前 K 个高频元素(Medium)(JAVA) 题目地址: https://leetcode.com/problems/t ...

  • LeetCode之Find All Numbers Disappeared in an Array

    LeetCode之Find All Numbers Disappeared in an Array

  • LeetCode 1128. 等价多米诺骨牌对的数量(简单)

    1128. 等价多米诺骨牌对的数量 给你一个由一些多米诺骨牌组成的列表 dominoes. 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的. ...

  • ​LeetCode刷题实战346:数据流中的移动平均值

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战260:只出现一次的数字 III

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战258:各位相加

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战256:粉刷房子

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战262:行程和用户

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战255:验证前序遍历序列二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战263:丑数

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战254:因子的组合

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...