我们如何将整数数组显示为一组范围？ (算法)
时间：2020-03-06 14:33:59 来源:igfitidea点击:
给定一个整数数组，最简单的方法是对其进行迭代并找出其涵盖的所有范围？例如，对于一个数组，例如：
$numbers = array(1,3,4,5,6,8,11,12,14,15,16);
范围是：
1,3-6,8,11-12,14-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);
输出：
1 3-6 8 11-12 14-16
我知道，这不是一个算法，但是我发现，在没有缩进问题的情况下，要真正地对其进行解释要比仅为其实现解决方案更难。
如果数组按升序排序，则问题很容易。定义一个" Range"结构或者类，它有一个开始和一个结束。然后遍历数组。如果当前元素比以前的元素大一个，则更新Range.end，否则用该元素创建一个新范围Range.begin。将范围存储到动态数组或者链接列表。或者只是随手打印出来。
如果数组可能未排序，请先对其进行排序。
第一：排序
第二：tokenise
然后：打印第一个值并在后续值上循环。如果"当前"值等于最后一个值+1，请跳过该值。否则，如果我们跳过了值，请打印破折号和值，否则，请打印逗号并重复。
那应该做。除非我们要我为我们编写作业代码？ :)
假设列表是有序的，那么我们可以从结尾开始，并继续减去下一个。差异为1时，我们处于范围内。如果不是，则开始一个新范围。
IE
16-15 = 1
15-14 = 1
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
}
}
14-12 = 2，范围是16-14开始新的范围。
# 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 = [ $_ ];
}
}
这是我的Perl解决方案。可以变得更干净，更快，但是它显示了它的工作原理：
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);
}
我在Java 1.5中的解决方案是：
[1, 3-6, 8, 11-12, 14-16]
输出：
加的特Greetz
我相信在1.5版本中引入Subversion的mergeinfo属性的格式与我们所要求的格式相同，因此我们可以查看Subversion的来源以了解它们的工作方式。如果它与已经在此处发布的其他建议有什么不同，我会感到惊讶。
如果按照示例对数组进行了排序，我将定义包含最小值和最大值的存储桶。
初始化：创建一个最小值和最大值等于第一个值的存储桶。
循环：将每个值与当前存储区的最大值进行比较。如果等于或者大于当前最大值1，则更新最大值。如果大于最大值大于1，请将存储桶保存到存储桶列表中，然后启动一个新存储桶。
最后，我们将获得一组带有最小值和最大值的存储桶。如果最小值与最大值相同，则打印一个数字(即：在示例中，第一个存储桶的最小值和最大值为1)。如果它们不同，则按范围打印。
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>
Lisp中的示例实现：
基本上，我们最终获得了一个东西列表，其中每个东西都有(最低存储桶，最高存储桶)。这些是范围。
如果列表尚未排序，请先对其进行排序。
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()
我将假设数组X()已预先排序(如果没有，则对数组进行预先排序)。
好吧，这就是我要做的。
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]]
创建一个简单的范围类型，其中包含范围值的开始/结束。添加一个仅包含一个值并设置start = end = value的构造函数。维护一堆范围对象，逐步处理数组的排序副本，扩展最大范围或者添加适当的新范围。更具体地说，当数组中的值为1 +堆栈的to上的范围对象的最终值时，增加该范围的最终值，否则，增加一个新范围(start = end = value at数组中的索引)。
这是我在Haskell拍摄的最好照片。
这是一种C3.0的实现方式：
- 自动属性(public int属性{get; set;})
- 使用新的对象初始化程序(新范围{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;
}
}
--
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;
}
大卫，干杯
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
输出：
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");
}
它类似于Python的版本。
/**
* $ 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
段落数量不匹配
