Hard-제목22:56.Merge Intervals
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. 제목 대의: 구간 집합을 제시하고 집합을 구한다.제목 분석: 공간이 바뀌면 먼저 하나의 수조를 열어 수축을 대표한다(반복적인 테스트를 거쳐 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;
}
}성적: 5ms, beats 98.15%, 중수 15ms, 18.26% cmershen의 잔소리: 사실 본 문제의 정상적인 방법은 구간 순서를 정하고 Comparator를 사용자 정의해야 한다. 나는 교묘한 방법을 사용했다. 물론 테스트 케이스의 데이터가 너무 약하기 때문이다. 만약에 데이터 범위가 4000이 아니라 4억이면 이 방법은 통하지 않는다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
