给定一个整数数组，最简单的方法是什么来遍历它并找出它所覆盖的所有范围？例如，对于这样的数组：
$numbers = array(1,3,4,5,6,8,11,12,14,15,16);
范围将是：
1,3-6,8,11-12,14-16
如何将整数数组显示为一组范围？（算法）
8
范围将是：
- Eran Galperin
1
无所谓，可以轻松解决。 - Eran Galperin
16个回答
14
如果数组按升序排序，则问题很容易解决。定义一个具有起始和结束的
Range结构或类。然后遍历数组。如果当前元素比前一个元素多1，则更新 Range.end ，否则使用此元素创建一个新的范围作为 Range.begin 。将范围存储到动态数组或链接列表中。或者在进行操作时直接打印它们。
如果数组未排序，则先对其进行排序。- Dima
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
我知道，我知道，这不是一个算法，但我发现如果没有缩进问题，很难解释它，所以我选择实现一个解决方案。
- lassevk
3
这是使用C# 3.0的方法：
要点如下：
- 自动属性（public int Property { get; set; }） - 使用新对象初始化程序（new Range { Begin = xxx; ... }） - 使用yield进行惰性评估 - 使用linq扩展方法（First()和Skip()）
要点如下：
- 自动属性（public int Property { get; set; }） - 使用新对象初始化程序（new Range { Begin = xxx; ... }） - 使用yield进行惰性评估 - 使用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;
}
}
你好，David
- VVS
2
第一步：排序 第二步：分词 然后：打印第一个值并循环遍历后续值。如果“当前”值等于上一个值+1，则跳过它。否则，如果您已经跳过该值，请打印破折号和该值，否则请打印逗号并重复。
就这样。除非你想让我帮你完成作业？ :)
- gbjbaanb
2
如果数组已排序（如您的示例），我会定义包含最小值和最大值的桶。
初始化：创建一个最小值和最大值都等于第一个值的桶。
循环：将每个值与当前桶的最大值进行比较。如果它等于当前最大值或比当前最大值多1，则更新最大值。如果它大于最大值1以上，则将该桶保存到桶列表中并启动一个新桶。
最后，您将拥有一组具有每个桶中的最小值和最大值的桶。如果最小值与最大值相同，则打印单个数字（例如，在您的示例中，第一个桶的最小值和最大值均为1）。如果它们不同，则打印为范围。
Lisp中的示例实现：
基本上你会得到一个事物列表，每个事物都有（最低桶值，最高桶值）。这些是您的范围。
如果列表尚未排序，请先对其进行排序。
初始化：创建一个最小值和最大值都等于第一个值的桶。
循环：将每个值与当前桶的最大值进行比较。如果它等于当前最大值或比当前最大值多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>
基本上你会得到一个事物列表，每个事物都有（最低桶值，最高桶值）。这些是您的范围。
如果列表尚未排序，请先对其进行排序。
- Morikal
1
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
- J.F. Sebastian
0
假设列表已经排序，您可以从末尾开始，并继续减去下一个。当差值为1时，您就处于一个范围内。否则，您将开始一个新范围。
i.e
16-15 = 1
15-14 = 1
14-12 = 2，范围为16-14 - 开始一个新的范围。
- Marc
1
只需要翻译文本内容，不要解释它：向前检查差异更好，可以更快访问缓存。注意如何处理最后一个范围。 - rlerallut
0
我相信在Subversion 1.5版本中引入的合并信息属性具有与您所要求的相同的格式，因此您可以潜在地查看Subversion的源代码以找出他们是如何实现的。我会很惊讶如果它与已经发布在这里的其他建议有任何不同。
- rmeador
0
我会假设数组X()已经预先排序（如果没有，先对数组进行排序）。
对于X()中的每个元素$element（使用$i作为当前数组位置）
将$element添加到数组Y()的末尾
如果（X($i)+1小于X($i+1)）且（$i+1不大于sizeof(X())），则
将Y(1)-Y(sizeof(Y()))附加到Z()的末尾
取消设置Y()
end if
下一个
如果Y()中仍有任何内容，则将其附加到Z()的末尾。
好吧，这就是我会做的方式。
- Valdemarick
0
创建一个简单的范围类型，其中包含范围值的起始/结束。添加一个构造函数，它只需要一个值并设置start = end = value。维护一个范围对象的堆栈，通过排序后的数组逐步处理，根据需要扩展顶部范围或添加新范围。更具体地说，当数组中的值为堆栈顶部范围对象的结束值加1时，增加该范围的结束值；否则，将一个新范围（其在数组中的索引处的start = end = value）推入堆栈。
- Wedge
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接