与えられた整数の配列を繰り返し処理し、それがカバーするすべての範囲を計算する最も簡単な方法は何ですか? たとえば、次のような配列の場合:
$numbers = array(1,3,4,5,6,8,11,12,14,15,16);
範囲は次のとおりです。
1,3-6,8,11-12,14-16
Eran Galperin
質問する
4795 次
16 に答える
14
配列が昇順でソートされている場合、問題は簡単です。Range始まりと終わりを持つ構造またはクラスを定義します。次に、配列を通過します。現在の要素が前の要素よりも 1 つ多い場合は を更新Range.endし、そうでない場合は、この要素を として新しい範囲を作成しますRange.begin。範囲を動的配列または連結リストに格納します。または、必要に応じて印刷してください。
配列がソートされていない可能性がある場合は、最初にソートします。
于 2008-09-22T21:21:38.430 に答える
3
これを行うC＃3.0の方法は次のとおりです。
興味がある点：
- 自動プロパティ（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;
}
}
乾杯、デビッド
于 2008-09-23T11:05:54.470 に答える
2
これは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
私は知っています、それはアルゴリズムではありませんが、解決策を実装するよりも、インデントの問題なしで実際に説明する方が難しいことがわかりました。
于 2008-09-22T21:21:23.143 に答える
2
first: sort second: tokenise then: 最初の値を出力し、後続の値をループします。「現在の」値が最後の値 +1 に等しい場合は、スキップします。それ以外の場合は、値の出力ダッシュと値をスキップした場合、そうでない場合はコンマを出力して繰り返します。
それはすべきです。宿題のコードを書いてほしくないなら？:)
于 2008-09-22T21:21:50.270 に答える
2
あなたの例のように配列がソートされている場合、最小値と最大値を含むバケットを定義します。
初期化: 最小値と最大値が最初の値に等しいバケットを作成します。
ループ: 各値を現在のバケットの最大値と比較します。現在の最大値以上である場合は、最大値を更新します。最大値よりも 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>
基本的に、最終的には、それぞれが持つもののリスト (バケット内の最小値、バケット内の最大値) になります。それらはあなたの範囲です。
リストがまだソートされていない場合は、最初にソートします。
于 2008-09-22T21:39:19.260 に答える
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
于 2008-10-24T14:38:17.503 に答える
0
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;
}
于 2008-09-24T23:37:29.007 に答える
0
これが私の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 = [ $_ ];
}
}
于 2008-09-22T21:32:35.067 に答える
0
Java1.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]
グリーツ、GHad
于 2008-09-22T21:35:14.670 に答える
0
範囲の開始/終了値を含む単純な範囲タイプを作成します。1つの値のみを取り、start = end=valueを設定するコンストラクターを追加します。範囲オブジェクトのスタックを維持し、配列のソートされたコピーを処理し、最上位の範囲を拡張するか、必要に応じて新しい範囲を追加します。より具体的には、配列の値が1 +スタックのtoにある範囲オブジェクトの終了値である場合、その範囲の終了値をインクリメントし、そうでない場合は、新しい範囲をプッシュします（start = end = value at配列内のインデックス）をスタックに追加します。
于 2008-09-22T21:55:11.953 に答える
0
パイソン (>= 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
于 2008-10-24T13:30:17.017 に答える
0
リストが順序付けられていると仮定すると、最後から開始して、次のものを減算し続けることができます。差は 1 ですが、範囲内です。そうでない場合は、新しい範囲を開始します。
すなわち
16-15 = 1
15-14 = 1
14-12 = 2、範囲は 16-14 - 新しい範囲を開始します。
于 2008-09-22T21:23:32.373 に答える
0
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]]
これがHaskellでの私のベストショットです。
于 2008-09-22T22:57:20.773 に答える
0
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
}
}
于 2008-09-22T21:26:49.527 に答える
0
1.5 リリースで Subversion に導入された mergeinfo プロパティは、あなたが求めているものと同じフォーマットを持っていると思います。すでにここに投稿されている他の提案とは異なる場合、私は驚かれることでしょう.
于 2008-09-22T21:39:11.197 に答える
0
配列 X() は事前にソートされていると仮定します (そうでない場合は、事前に配列をソートします)。
X() の各要素を $element として ($i を現在の配列位置として)
配列 Y() の末尾に $element を追加します
(X($i) + 1 が X($i + 1) より小さい) AND ($i + 1 が sizeof(X()) より大きくない) の場合
Y(1)."-".Y(sizeof(Y())) を Z() の末尾に追加
Y() の設定を解除
終了する場合
次
Y() に何か残っている場合は、Z() の末尾に追加します
まあ、それは私がそれを行う方法です。
于 2008-09-22T21:43:05.680 に答える