ソートされた配列に間隔を作成する

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インデックスからの1つのループ、配列の中間からの2つのループ、およびその終わりからの1つのループ。すべてのループは現在の要素と次の要素のdiffが1であるかどうかをチェックし、そうであれば次の要素に進み、それ以外の要素から間隔を作成して次の要素から新しい間隔を開始します。

私の質問はそれは良いアプローチですか、それとも良い方法がありますか？疑似コードまたはJavaコードを入力してください。

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

あなたは、このような概念を表現するためにはApache CommonsのからIntRangeの配列を持つ検討することができます。

はい、サードパーティのライブラリが必要ですが、結局Apache Commonsです。

Answer 3

連続した整数のリストを取得しようとしています。

O（n）ので最も単純で素朴な方法は、このような何かを行うことです。

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に適応することができます。