p352

发表于 | 分类于 |

LeetCode p352 Data Stream as Disjoint Intervals 题解

1.题目：

Given a data stream input of non-negative integers a1, a2, …, an, …, 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]

题意：使用add方法输入一些数，getIntervals方法在输入的数中分成若干个连续的区间输出，尽可能使区间变少。

2.解题思路:

。。第一次没有时候HashMap超时了，小优化之后就AC了。
思路没有什么太大的变化。先将存有的单个区间进行排序，再判断相邻区间是否可以连通即可。注意循环结束之后还要加上最后一个区间。

3.代码

[title] [] [url] [link text]
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class SummaryRanges {

    /** Initialize your data structure here. */
    public SummaryRanges() {
        
    }
    public ArrayList<Interval> arrayList = new ArrayList<Interval>();
	public HashSet<Integer> hashSet = new HashSet<Integer>();
    public void addNum(int val) {
        if (!hashSet.contains(val)) {
			hashSet.add(val);
			Interval interval = new Interval();
			interval.start = val;
			interval.end = val;
			arrayList.add(interval);
		}
    }
    
    public List<Interval> getIntervals() {
        List<Interval> ans = new ArrayList<Interval>();
		Collections.sort(arrayList, new Comparator<Interval>() {
			public int compare(Interval l1, Interval l2) {
				return l1.start - l2.start;
			}
		});
		int len = arrayList.size();
		int start = arrayList.get(0).start;
		int end = arrayList.get(0).end;
		
		for (int i = 1; i < len; i++) {
			if (end + 1 == arrayList.get(i).start) {
				end = arrayList.get(i).end;
				continue;
			} else {
				Interval interval = new Interval();
				interval.start = start;
				interval.end = end;

				ans.add(interval);
				start = arrayList.get(i).start;
				end = arrayList.get(i).end;
			}

		}
		Interval interval = new Interval();
		interval.start = start;
		interval.end = end;
		ans.add(interval);
		
//		for (Interval i : ans) {
//
//			System.out.println(i.start + "   " + i.end);
//		}
		return ans;
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * List<Interval> param_2 = obj.getIntervals();
 */

4.一些总结：