如何将整数数组显示为一组范围？(算法)

Question

给定一个整数数组，迭代它并计算出它覆盖的所有范围的最简单方法是什么？例如，对于像这样的数组：

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

范围将是：

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

Answer 1

如果数组按升序排序，那么问题就简单了。定义一个Range结构或类，它有开头和结尾。然后遍历数组。如果当前元素比前一个元素多一个，则更新Range.end，否则使用此元素作为Range.begin创建一个新范围。将范围存储到动态数组或链表中。或者直接把它们打印出来。

如果数组可能无法排序，则先对其排序。

Answer 2

这是一种类似于C# 3.0的方式：

兴趣点：

• 自动属性(public int Property { get；set；})
• 使用新的对象初始值设定项(new Range { Begin = xxx；... }
• 使用yield lazy evaluation
• using linq扩展方法(First()和Skip())

-

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

干杯，大卫

Answer 3

下面是一个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

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