Java实现 LeetCode 352 将数据流变为多个不相交区间

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java实现 LeetCode 352 将数据流变为多个不相交区间，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2370字，纯文字阅读大概需要4分钟。

内容图文

352. 将数据流变为多个不相交区间

给定一个非负整数的数据流输入 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]

进阶：
如果有很多合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

提示：
特别感谢 @yunhong 提供了本问题和其测试用例。

class SummaryRanges {

  
    private List<int[]> list = new ArrayList<>();

    /** Initialize your data structure here. */
    public SummaryRanges() {
    }

    public void addNum(int val) {
        if (list.size() == 0) {
            int[] arr = new int[2];
            arr[0] = arr[1] = val;
            list.add(arr);
            return;
        }

        int insertPosition = findInsertPosition(val);
        if (insertPosition == list.size()) {
            if (val == list.get(list.size() - 1)[1] + 1) {
                list.get(list.size() - 1)[1] = list.get(list.size() - 1)[1] + 1;
            } else {
                int[] arr = new int[2];
                arr[0] = arr[1] = val;
                list.add(arr);
            }
        } else if (insertPosition == 0) {
            if (val == list.get(0)[0] - 1) {
                list.get(0)[0] = list.get(0)[0] - 1;
            } else {
                int[] arr = new int[2];
                arr[0] = arr[1] = val;
                list.add(0, arr);
            }
        } else if (insertPosition > 0) {
            if (val == list.get(insertPosition)[0] - 1 && val == list.get(insertPosition - 1)[1] + 1) {
                int index = insertPosition - 1;
                int[] front = list.get(index);
                int[] behind = list.get(insertPosition);

                list.remove(index);
                list.remove(index);

                int[] arr = new int[2];
                arr[0] = front[0];
                arr[1] = behind[1];
                list.add(index, arr);
            } else if (val == list.get(insertPosition)[0] - 1) {
                list.get(insertPosition)[0] = list.get(insertPosition)[0] - 1;
            } else if (val == list.get(insertPosition - 1)[1] + 1) {
                list.get(insertPosition - 1)[1] = list.get(insertPosition - 1)[1] + 1;
            } else {
                int[] arr = new int[2];
                arr[0] = arr[1] = val;
                list.add(insertPosition, arr);
            }
        }
    }

    public int[][] getIntervals() {
        int[][] result = new int[list.size()][];

        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    private int findInsertPosition(int val) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left + right) / 2;
            if (val >= list.get(mid)[0] && val <= list.get(mid)[1]) return -1;

            if (val < list.get(mid)[0]) right = mid;
            else if (val > list.get(mid)[1]) left = mid + 1;
        }

        return left;
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * int[][] param_2 = obj.getIntervals();
 */

内容总结

以上是互联网集市为您收集整理的Java实现 LeetCode 352 将数据流变为多个不相交区间全部内容，希望文章能够帮你解决Java实现 LeetCode 352 将数据流变为多个不相交区间所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端