代码之家 › 专栏 › 技术社区 › Eran Galperin

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

range language-agnostic arrays algorithm

Eran Galperin · 技术社区 · 16 年前

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

范围将是:

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

16 回复 | 直到 16 年前

Dima 16 年前

如果数组按升序排序,那么问题就容易了。定义一个 Range 结构或类,有开始和结束。然后遍历数组。如果当前元素比上一个元素多一个,则更新 Range.end ,否则创建一个新范围,并将此元素作为 Range.begin

VVS 14 年前

这里有一个C#3.0'y的方法:

关注点:

使用新的对象初始值设定项(新范围{Begin=xxx;…}
使用收益率进行延迟评估
使用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;
    }
}

干杯,大卫

Lasse V. Karlsen 16 年前

这是一个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);

我知道,我知道,这不是算法 ,但我发现在没有缩进问题的情况下真正解释它比仅仅实现一个解决方案要困难得多。

gbjbaanb 16 年前

第一:分类然后:打印第一个值并循环后续值。如果“当前”值等于最后一个值+1,则跳过它。否则,如果跳过了值打印破折号和值,则打印逗号并重复。

这样就可以了。除非你想让我帮你写作业?:)

Morikal 16 年前

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

初始化:创建一个最小值和最大值分别等于第一个值的bucket。

循环:将每个值与当前桶的最大值进行比较。如果它等于或大于当前最大值1,则更新最大值。如果它大于最大值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>

基本上你会得到一个清单,每个东西都有(最低的在桶里,最高的在桶里)。这些是你的范围。

如果列表尚未排序,请先对其排序。

Community CDub 7 年前

C(gcc)

它类似于 the Python's version

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

MarcE 16 年前

假设列表是有序的,你可以从末尾开始,然后继续减去下一个。当差值为1时,您处于一个范围内。如果不是,你就开始一个新的范围。

即

15-14 = 1

benPearce 16 年前

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

jkramer 16 年前

这是我的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 = [ $_ ];
    }
}

GHad 16 年前

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

格里茨,加德

rmeador 16 年前

我相信在1.5版本中引入Subversion的mergeinfo属性的格式与您所要求的格式相同,因此您可以查看Subversion的源代码,以了解他们是如何做到这一点的。如果它与已经发布在这里的其他建议有什么不同,我会感到惊讶。

Valdemarick 16 年前

我将假定数组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()

好吧,我会这样做的。

Wedge 16 年前

axblount 16 年前

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

这是我在哈斯克尔最好的机会。

Community CDub 4 年前

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

Community CDub 4 年前

Python(>=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