Hard-テーマ22:56.Merge Intervals
3506 ワード
Given a collection of intervals,merge all overlapping intervals.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. 区間集合を与え、並列集合を求める.题目分析:空间は时间を変えて、まず1つの配列を开いて数轴を代表して(缲り返しテストして4000まで开けて十分です)、それから元の集合の中の数を记录して、更にこの配列をスキャンして、新しい区间を记录すればいいです.注意しなければならないのは単点の情況があって、もし伝統的なojが直接waを与えるならば本当にどうすればいいか分かりません...ソース:(language:java)
成績:5 ms、beats 98.15%、衆数15 ms、18.26%cmershenの砕けた考え:実は、本題の正常なやり方は区間のソートに対して、1つのComparatorをカスタマイズするべきで、私は巧みな方法を採用して、もちろんtest caseのデータが弱すぎるためで、データの範囲が4000ではなく4億であれば、この方法は通じません.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. 区間集合を与え、並列集合を求める.题目分析:空间は时间を変えて、まず1つの配列を开いて数轴を代表して(缲り返しテストして4000まで开けて十分です)、それから元の集合の中の数を记录して、更にこの配列をスキャンして、新しい区间を记录すればいいです.注意しなければならないのは単点の情況があって、もし伝統的なojが直接waを与えるならば本当にどうすればいいか分かりません...ソース:(language:java)
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
boolean[] x = new boolean[4000];
boolean[] dots = new boolean[4000];
int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
List<Interval> list = new ArrayList<Interval>();
for(Interval interval : intervals) {
for(int i=interval.start;i<interval.end;i++) {
x[i]=true;
if(i<min)
min=i;
if(i>max)
max=i;
}
}
int i = min;
while(i<=max) {
if(!x[i]) {
i++;
continue;
}
int start=i,end=start;
while(x[end])
end++;
list.add(new Interval(start,end));
i=end;
}
for(Interval interval : intervals) {
int start = interval.start,end = interval.end;
if(start==end && !dots[interval.start]) {
dots[start] = true;
if(start==0 && !x[0])
list.add(new Interval(start, end));
else if(!x[start] && !x[start-1])
list.add(new Interval(start, end));
}
}
return list;
}
}
成績:5 ms、beats 98.15%、衆数15 ms、18.26%cmershenの砕けた考え:実は、本題の正常なやり方は区間のソートに対して、1つのComparatorをカスタマイズするべきで、私は巧みな方法を採用して、もちろんtest caseのデータが弱すぎるためで、データの範囲が4000ではなく4億であれば、この方法は通じません.