정렬 된 배열에 간격 만들기

Question

{1, 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 21, 23, 25, 26}의 정렬 된 배열이 있다고 가정 해 봅니다. 현실에서

1..5 
7..10 
15..16 
21..21 
23..23 
25..26 

내가 훨씬 더 큰 데이터를, 그래서 나는 좋은 런타임과 알고리즘을 필요 : 나는 간격으로 다음과 같은 방법을 이러한 요소를 넣어 싶습니다.

내가 생각한 것은 다음과 같습니다. 배열을 2 부분으로 분리하고 4 루프가 배열을 통과합니다. 0 인덱스에서 하나의 루프, 배열 중간에서 2 루프, 끝에서 1 루프. 모든 루프는 현재 요소와 다음 요소의 diff가 1인지 확인하고, 예이면 다음 요소로 이동하고, 이전 요소와의 간격을 만들고 다음 요소에서 새 간격을 시작합니다.

제 질문은 좋은 접근 방법입니까 아니면 더 좋은 방법입니까? 제발 의사 또는 자바 코드.

Answer 1

선형 솔루션 :

int intervalStart = a[0]; 
for (int i = 1; i < a.length; ++i) { 
    if (a[i] > a[i-1] + 1) { 
     outputInterval(intervalStart, a[i-1]); 
     intervalStart = a[i]; 
    } 
} 
outputInterval(intervalStart, a[a.length-1]); 

의 Runnable 버전 : https://ideone.com/NZ2Uex

Answer 2

당신은 이러한 개념을 표현하기 위해 아파치 공용 IntRange의 배열을 가진 고려할 수 있습니다.

예, 제 3 자 라이브러리가 필요하지만 결국 Apache Commons입니다.

Answer 3

연속 정수 목록을 가져 오려고합니다.

List<List<Integer>> list_of_sublists = new List<>(); // The list of sublists 
int lastElement = elements[0]; 
List<Integer> subList = new List <>(); // The current sublist 
subList.add(lastElement); 
int i = 1; // We start with index 1 because index 0 is already done 
while (i < elements.length){ 
    int element = elements[i] 
    if !(lastElement + 1 == element)){ //If not a consecutive we start a new list 
     list_of_sublists.add(subList); 
     subList = new List<>(); 
    } 
    lastElement = element; 
    subList.add(element); 
    i ++; 

//We didn't add the last sublist 
list_of_sublists.add(subList); 
return list_of_sublists; 

쉽게 간격을 받고 복사는 각 간격을 afterwars에 의해 arrays에 적응할 수 :

는 O (n)이에서 가장 간단하고 순진 방법은 같은 것을 할 것입니다.