ChunNote
0%

leetCode-352:Data Stream as Disjoint Intervals

发表于 分类于

问题描述

要求实现一个类，类的功能是将输入的数字转成合并后的区间。题目链接：**点我**

样例输入输出

输入：

[“SummaryRanges”, “addNum”, “getIntervals”, “addNum”, “getIntervals”, “addNum”, “getIntervals”, “addNum”, “getIntervals”, “addNum”, “getIntervals”]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]

输出：

[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

解释：

SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1); // arr = [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3); // arr = [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7); // arr = [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

问题解法

用一个 List 保存合并后的区间，每次放入数字时就对 List 中的数组进行计算更新。代码如下

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
class SummaryRanges {
    List<int[]> intervals = new ArrayList<>();

    public SummaryRanges() {

    }

    public void addNum(int value) {
        int[] nums = {value, value};
        List<int[]> temp = new ArrayList<>();
        for (int i = 0; i < intervals.size(); i++) {
            int[] interval = intervals.get(i);
            
            // solution for duplicate number
            if (interval[0] <= value && value <= interval[1]) {
                return;
            }
            
            if (interval[1] < value - 1) {
                temp.add(interval);
                continue;
            }

            if (interval[0] == value + 1) {
                nums[1] = interval[1];
                continue;
            }

            if (interval[1] == value - 1) {
                nums[0] = interval[0];
                continue;
            }

            temp.add(nums);
            nums = interval;
        }

        temp.add(nums);
        intervals = temp;
    }

    public int[][] getIntervals() {
        return intervals.toArray(new int[intervals.size()][2]);
    }
}
/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(value);
 * int[][] param_2 = obj.getIntervals();
 */