Как бы вы отобразили массив целых чисел в виде набора диапазонов? (алгоритм)

Question

Учитывая массив целых чисел, как проще всего перебрать его и выяснить все диапазоны, которые он охватывает? например, для массива, такого как:

$numbers = array(1,3,4,5,6,8,11,12,14,15,16);

Диапазоны будут:

 1,3-6,8,11-12,14-16

Answer 1

Я буду считать, что массив X () предварительно отсортирован (и, если нет, отсортируйте массив заранее).

for each element of X() as $element (with $i as current array posistion)
    add $element to end of array Y()
    if (X($i) + 1 is less than X($i + 1)) AND ($i + 1 is not greater than sizeof(X())) then
        append Y(1)."-".Y(sizeof(Y())) to end of Z()
        unset Y()
    end if    
next
if anything remains in Y() append to end of Z()

ну вот как бы я это сделал.

Answer 2

Я полагаю, что свойство mergeinfo, которое было введено в Subversion в выпуске 1.5, имеет формат, совпадающий с тем, что вы запрашиваете, так что вы можете просмотреть источник Subversion и выяснить, как они это делают. , Я был бы удивлен, если это отличается от других предложений, которые уже были размещены здесь.

Answer 3

Мое решение в Java 1.5 будет:

public static List<String> getRanges(int... in) {
    List<String> result = new ArrayList<String>();
    int last = -1;
    for (int i : in) {
        if (i != (last + 1)) {
            if (!result.isEmpty()) {
                addRange(result, last);
            }
            result.add(String.valueOf(i));
        } 
        last = i;
    }
    addRange(result, last);
    return result;
}

private static void addRange(List<String> result, int last) {
    int lastPosition = result.size() - 1;
    String lastResult = result.get(lastPosition);
    if (!lastResult.equals(String.valueOf(last))) {
        result.set(lastPosition, lastResult + "-" + last);
    }
}

public static void main(String[] args) {
    List<String> ranges = getRanges(1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16);
    System.out.println(ranges);
}

который выводит:

[1, 3-6, 8, 11-12, 14-16]

Greetz, GHad

Answer 4

Вот мое решение Perl. Может быть чище и быстрее, но показывает, как это работает:

# Just in case it's not sorted...
my @list = sort { $a <=> $b } ( 1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16 );

my $range = [ $list[0] ];

for(@list[1 .. $#list]) {
    if($_ == $range->[-1] + 1) {
        push @$range, $_;
    }
    else {
        print $#$range ? $range->[0] . '-' . $range->[-1] : $range->[0], "\n";
        $range = [ $_ ];
    }
}

Answer 5

startRange = array[0];    
for(i=0;i<array.length;i++)
{
   if (array[i + 1] - array[i] > 1)
   {
     endRange = array[i];
     pushRangeOntoArray(startRange,endRange);
     i++;
     startRange = array[i]
     // need to check for end of array here
   }
}

Answer 6

Если список упорядочен, вы можете начать с конца и продолжать вычитать следующий. Хотя разница равна 1, вы находитесь в диапазоне. Когда это не так, вы начинаете новый диапазон.

т.е.

16-15 = 1

15-14 = 1

14-12 = 2, диапазон 16-14 - начать новый диапазон.