您怎么会显示一系列整数作为一套范围？(算法)

StackOverflow https://stackoverflow.com/questions/117691

题

鉴于一系列整数，什么是最简单的方法来迭代过它，并找出所有的范围，它涵盖了?例如，对于一系列诸如：

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

范围将是：

 1,3-6,8,11-12,14-16
有帮助吗？

解决方案

如果数组按升序排序，则问题很简单。定义 Range 结构或类，它有一个开头和一个结尾。然后浏览阵列。如果当前元素比前一个元素多一个，则更新 Range.end ，否则使用此元素创建一个新范围 Range.begin 。将范围存储到动态数组或链接列表。或者只是随时打印出来。

如果数组可能没有排序，则先排序。

其他提示

这里是C#3.0'y方式这样做:

的兴趣点：

  • 自动性(公共int酒店{获得；集；})
  • 使用新的对象的初始化(新范围{开始=xxx;...}
  • 使用率为懒惰的评价
  • 使用皇宫的扩展方法(第一()跳过())

-

class Demo
{
    private class Range
    {
        public int Begin { get; set; }
        public int End { get; set; }

        public override string ToString()
        {
            if (Begin == End)
                return string.Format("{0}", Begin);
            else
                return string.Format("{0}-{1}", Begin, End);
        }
    }

    static void Main(string[] args)
    {
        var list = new List<int> { 1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16 };
        // list.Sort();
        var ranges = GetRangesForSortedList(list);

        PrintRange(ranges);

        Console.Read();
    }

    private static void PrintRange(IEnumerable<Range> ranges)
    {
        if (ranges.Count() == 0)
            return;

        Console.Write("[{0}", ranges.First());

        foreach (Range range in ranges.Skip(1))
        {
            Console.Write(", {0}", range);
        }

        Console.WriteLine("]");
    }

    private static IEnumerable<Range> GetRangesForSortedList(IList<int> sortedList)
    {
        if (sortedList.Count < 1) 
            yield break;

        int firstItem = sortedList.First();
        Range currentRange = new Range { Begin = firstItem, End = firstItem };

        foreach (int item in sortedList.Skip(1))
        {
            if (item == currentRange.End + 1)
            {
                currentRange.End = item;
            }
            else
            {
                yield return currentRange;
                currentRange = new Range { Begin = item, End = item };
            }
        }

        yield return currentRange;
    }
}

欢呼声,大卫

这是一个python实现，应该很容易遵循

numbers = [1,3,4,5,6,8,11,12,14,15,16];

def is_predecessor(i1, i2):
    if i1 == i2 - 1:
        return True;
    else:
        return False;

def make_range(i1, i2):
    if i1 == i2:
        return str(i1);
    else:
        return str(i1) + "-" + str(i2);

previous_element = None;
current_start_element = None;

for number in numbers:
    if not is_predecessor(previous_element, number):
        if current_start_element is not None:
            print make_range(current_start_element, previous_element);
        current_start_element = number;
    previous_element = number;

# handle last pair
if current_start_element is not None:
    print make_range(current_start_element, previous_element);

输出：

1
3-6
8
11-12
14-16

我知道，我知道，它不是算法，但我发现在没有缩进问题的情况下实际解释它比仅为其实现解决方案更难。

首先：排序 第二：令牌 然后：打印第一个值并循环后续值。如果“当前”值等于最后一个值+1，请跳过它。否则，如果您已跳过值打印短划线和值，否则打印逗号并重复。

应该这样做。除非你想让我为你编写作业代码？ ：）

如果数组已排序，如您的示例所示，我将定义包含最小值和最大值的存储桶。

初始化：创建一个最小值和最大值等于第一个值的存储桶。

循环：将每个值与当前存储桶的最大值进行比较。如果它等于或大于当前最大值1，则更新最大值。如果它大于最大值1，请将存储桶保存到存储桶列表并启动新存储桶。

最后，你将拥有一组每个都有最小值和最大值的桶。如果min与max相同，则打印一个数字（例如：在您的示例中，第一个桶的最小值为1，最大值为1）。如果它们不同，则打印为范围。

lisp中的示例实现：

CL-USER> (defun print-ranges (integer-list)
           (let ((sorted-list (sort integer-list #'<)))
             (loop with buckets = ()
                   with current-bucket
                   for int in sorted-list
                     initially (setf current-bucket (cons (first sorted-list) (first sorted-list)))
                   do (cond ((= int (cdr current-bucket))) ; do nothing, this number is already in range
                            ((= (1- int) (cdr current-bucket)) ; number is 1 higher--update bucket's max
                             (setf (cdr current-bucket) int))
                            (t
                             (push current-bucket buckets)
                             (setf current-bucket (cons int int)))) ; set up a new bucket
                   finally (push current-bucket buckets)
                           (loop for firstp = t then nil
                                 for bucket in (nreverse buckets) do
                                   (cond ((= (car bucket) (cdr bucket))
                                          (format t "~:[,~;~]~D" firstp (car bucket)))
                                         (t
                                          (format t "~:[,~;~]~D-~D" firstp (car bucket) (cdr bucket))))))))
PRINT-RANGES
CL-USER> (print-ranges (list 1 3 4 5 6 8 11 12 14 15 16))
1,3-6,8,11-12,14-16
NIL
CL-USER>

基本上你最终会得到一个东西列表，其中每个东西都有（桶中最低，桶中最高）。那些是你的范围。

如果列表尚未排序，请先对其进行排序。

C（gcc）

类似于 Python的版本。

void ranges(int n; int a[n], int n)
{
  qsort(a, n, sizeof(*a), intcmp);
  for (int i = 0; i < n; ++i) {
    const int start = i;
    while(i < n-1 and a[i] >= a[i+1]-1)
      ++i;
    printf("%d", a[start]);
    if (a[start] != a[i])
      printf("-%d", a[i]);
    if (i < n-1)
      printf(",");
  }
  printf("\n");
}

示例：

/**
 * $ gcc -std=c99 -Wall ranges.c -o ranges && ./ranges
 */
#include <iso646.h> // and
#include <stdio.h>
#include <stdlib.h>

#define T(args...)                                              \
  {                                                             \
    int array[] = {args};                                       \
    ranges(array, sizeof(array) / sizeof(*array));              \
  }

int intcmp(const void* a, const void* b)
{
  const int *ai = a;
  const int *bi = b;

  if (*ai < *bi)
    return -1;
  else if (*ai > *bi)
    return 1;
  else
    return 0;
}

int main(void)
{
  T(1,3,4,5,6,8,11,12,14,15,16);
  T();
  T(1);
  T(1, 2);
  T(3, 1);
  T(1, 3, 4);
  T(1, 2, 4);
  T(1, 1, 2, 4);
  T(1, 2, 2, 4);
  T(1, 2, 2, 3, 5, 5);
}

输出：

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

1
1-2
1,3
1,3-4
1-2,4
1-2,4
1-2,4
1-3,5

假设列表已经订购，您可以从最后开始并继续减去下一个列表。虽然差异是1，但你在一个范围内。当它不是时，你开始一个新的范围。

即

16-15 = 1

15-14 = 1

14-12 = 2，范围是16-14 - 开始一个新范围。

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
   }
}

这是我的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(
这是我的Perl解决方案。可以更干净，更快，但它显示了它的工作原理：


<*> == $range->[-1] + 1) {
        push @$range, 
这是我的Perl解决方案。可以更干净，更快，但它显示了它的工作原理：


<*>;
    }
    else {
        print $#$range ? $range->[0] . '-' . $range->[-1] : $range->[0], "\n";
        $range = [ 
这是我的Perl解决方案。可以更干净，更快，但它显示了它的工作原理：


<*> ];
    }
}

我在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

我相信1.5版本中引入Subversion的mergeinfo属性的格式与您要求的格式相同，因此您可以查看Subversion的源代码以了解它们是如何进行的。如果它与已在此处发布的其他建议有任何不同，我会感到惊讶。

我将假设数组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()
好吧，我就是这样做的。

创建一个包含范围值开始/结束的简单范围类型。添加一个只接受一个值并设置start = end = value的构造函数。维护一堆范围对象，按照数组的排序副本工作，扩展顶部范围或根据需要添加新范围。更具体地说，当数组中的值是堆栈的to的范围对象的结束值的1 +时，增加该范围的结束值，如果不是，则推送一个新的范围（start = end = value at数据中的索引）到堆栈上。

module Main where

ranges :: [Int] -> [[Int]]
ranges [] = []
ranges list@(x:xs) = let adj = adjacent list in
             let len = length adj in
                 if length adj == 1
                then [[x]] ++ ranges xs
                else [[x,(last adj)]] ++ ranges (drop ((length adj) - 1) xs)
    where adjacent [] = []
          adjacent (x:xs) = if (xs /= []) && (x + 1) == head xs
             then [x] ++ adjacent (xs)
             else [x]

main = do putStrLn $ show $ ranges [1,2,3,4,5,6,8,11,12,14,15,16]

-- Output: [[1,6],[8],[11,12],[14,16]]

这是我在哈斯克尔拍摄的最佳镜头。

Perl 6 

sub to_ranges( Int *@data ){
  my @ranges;

  OUTER: for @data -> $item {
    for @ranges -> $range {
      # short circuit if the $item is in a range
      next OUTER if $range[0] <= $item <= $range[1];

      given( $item ){
        when( $range[0]-1 ){ $range[0] = $item }
        when( $range[1]+1 ){ $range[1] = $item }
      }
    }

    push @ranges, [$item,$item];
  }

  return @ranges;
}

Python（＆gt; = 2.6）

此版本另外处理重复和未排序的序列。

from __future__ import print_function

def ranges(a):
    a.sort()
    i = 0
    while i < len(a):
        start = i
        while i < len(a)-1 and a[i] >= a[i+1]-1:
            i += 1
        print(a[start] if a[start] == a[i] else "%d-%d" % (a[start], a[i]),
              end="," if i < len(a)-1 else "\n")
        i += 1

示例：

import random
r = range(10)
random.shuffle(r)
ranges(r)
ranges([1,3,4,5,6,8,11,12,14,15,16]);
ranges([])
ranges([1])
ranges([1, 2])
ranges([1, 3])
ranges([1, 3, 4])
ranges([1, 2, 4])
ranges([1, 1, 2, 4])
ranges([1, 2, 2, 4])
ranges([1, 2, 2, 3, 5, 5])

输出：

0-9
1,3-6,8,11-12,14-16
1
1-2
1,3
1,3-4
1-2,4
1-2,4
1-2,4
1-3,5
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top