是否有专门的算法来折叠(聚合)集合中缺失的数字？

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(arrayi+1-arrayi > 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+1作为arr[]的最后一个值。