algorithm - セット内の欠落した数値を折りたたむ (集計する) 特殊なアルゴリズムはありますか?

Question

それは整数の配列です[3, 4, 5, 10, 10000] のような配列/リストに変換し['1, 2', 3, 4, 5, '6-9', 10, '11-9999', 10000]ます。これは小さな例ですが、1 から 10000 までのすべての数値をループするのは効果的でないことは明らかです。

Answer 1

配列がソートされていると仮定すると、すべては次のようになります。

for i = 0 ... array.Length-1
  write array[i]
  switch( array[i+1] - array[i])
    case 1:
      do nothing;
    case 2:
      write "'" + (array[i]+1) + "'";
    case 3:
      write "'" + (array[i]+1) + " , " + (array[i]+2) + "'"
    default:
      write "'" + (array[i]+1) + " - " + (array[i+1]-1) + "'"
write array[array.Length]

注：さまざまなスイッチは、欠落しているアイテムを含む新しい配列の「プレゼンテーション」に固執することです。それが必要ない場合は、単に if(array[i+1]-array[i] > 1) を口に出してください

Answer 2

初期配列を arr[] とし、arr の長さを N とします。したがって、アルゴリズムは次のようになります。

for(i=0;i<N-1;i++){
    if(ar[i+1]-ar[i]!=1){
        add segment ar[i]+1 to ar[i+1]-1 to new array
    }
    add arr[i] to new array
}

10000+1arr[] の最後の値として追加する必要があることに注意してください。