Wie würden Sie ein Array von ganzen Zahlen als eine Reihe von Bereichen angezeigt werden? (Algorithmus)
https://stackoverflow.com/questions/117691
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
ein Array von ganzen Zahlen gegeben, was ist der einfachste Weg, darüber iterieren und alle Bereiche herauszufinden, es deckt? beispielsweise für eine Anordnung, wie beispielsweise:
$numbers = array(1,3,4,5,6,8,11,12,14,15,16);
Die Bereiche seien:
1,3-6,8,11-12,14-16
Lösung
Wenn das Array in aufsteigender Reihenfolge sortiert ist, dann ist das Problem einfach. Definieren einer Range Struktur oder Klasse, die einen Anfang und ein Ende hat. Dann gehen Sie durch das Array. Wenn das aktuelle Element eine mehr als die vorherigen, update Range.end ist, sonst eine neue Reihe mit diesem Element als Range.begin erstellen. Speichern die Bereiche zu einem dynamischen Array oder einer verknüpften Liste. Oder sie einfach ausdrucken, wie Sie gehen.
Wenn das Array nicht sortiert werden kann, ist es dann zuerst sortieren.
Andere Tipps
Hier ist eine C # 3.0'y Art und Weise tun:
Points of Interest:
- automatische Eigenschaften (public int Property {get; set;})
- mit neuen Objektinitialisierer (neuen Range {Start = xxx; ...}
- mit Ertrag für lazy evaluation
- mit Linq-Erweiterungsmethoden (First () und 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;
}
}
Cheers, David
Hier ist eine Python-Implementierung, sollte es einfach genug sein, folgen
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);
Diese Ausgänge:
1
3-6
8
11-12
14-16
Ich weiß, ich weiß, es ist nicht ein Algorithmus , aber ich fand es schwieriger, es tatsächlich zu erklären, ohne als Vertiefung Probleme mit nur eine Lösung für sie umzusetzen.
zuerst: sort Zweitens: tokenise dann: den ersten Wert und die Schleife über nachfolgend diejenigen drucken. Wenn der ‚aktuellen‘ Wert auf den letzten Wert gleich +1 ist, überspringen Sie es. Andernfalls, wenn Sie Wert Druck Bindestrich und den Wert übersprungen haben, sonst ein Komma und wiederholen Sie drucken.
Das sollte tun. Es sei denn, Sie wollten, dass ich Ihre Hausaufgaben für Sie kodieren up? :)
Wenn das Array sortiert wird, wie in Ihrem Beispiel würde ich Eimer definiert eine min und max enthalten.
initialisieren. Erstellen Sie einen Eimer mit min und max gleich dem ersten Wert
Loop: Vergleichen Sie jeden Wert mit dem max des aktuellen Eimer. Wenn er gleich oder 1 mehr als der aktuelle max ist, aktualisieren Sie den max. Wenn es mehr als 1 größer ist als der max ist, die Schaufel auf eine Liste von Eimern speichern und einen neuen Eimer starten.
Am Ende werden Sie eine Reihe von Eimern mit min haben und max in jedem. Wenn die min das gleiches wie der max ist, drucken Sie eine einzelne Nummer (zB: in Ihrem Beispiel wäre der erste Eimer eine min und max von 1 hat). Wenn sie unterschiedlich sind, als ein Bereich drucken.
Beispiel-Implementierung in 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>
Im Grunde genommen am Ende mit einer Liste von Dingen, wo jedes Ding (niedrigste-in-Eimer, am höchsten in-Eimer) hat. Das sind Ihre Bereiche.
Wenn die Liste nicht bereits sortiert, sortieren Sie es zuerst.
C (gcc)
Es ist ähnlich wie die Version 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");
}
Beispiel:
/**
* $ 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);
}
Ausgabe:
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
Unter der Annahme der Liste bestellt man am Ende beginnen könnte und halten Sie die nächste Subtraktion nach unten. Während der Unterschied 1 ist, sind Sie in einem Bereich. Wenn es nicht ist, starten Sie einen neuen Bereich.
das heißt
16-15 = 1
15-14 = 1
14-12 = 2 ist der Bereich von 16 bis 14 - eine neue Reihe beginnen
.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
}
}
Hier ist meine Perl-Lösung. Könnte sein, saubere und schneller, aber es zeigt, wie es funktioniert:
# 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 = [ $_ ];
}
}
Meine Lösung in Java 1.5 wäre:
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);
}
, welche Ausgänge:
[1, 3-6, 8, 11-12, 14-16]
Greetz, ghad
Ich glaube, die mergeinfo Eigenschaft, der Subversion in der Version 1.5 eingeführt wurde, ein Format hat, das das gleiche ist wie das, was Sie für Fragen, so dass Sie möglicherweise Blick durch die Quelle von Subversion gehen könnten, um herauszufinden, wie sie es tun . Ich wäre überrascht, wenn seine anders als die anderen Vorschläge, die bereits hier gepostet wurden.
Ich werde das Array X annehmen () ist vorsortiert (und wenn nicht, sortieren das Array vor-Hand).
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()
gut, das ist, wie ich es tun würde.
Erstellen Sie einen einfachen Bereichstyp, die Anfang / Ende des Bereichswertes enthält. Fügen Sie einen Konstruktor, der nur einen Wert und setzt start = end = Wert annimmt. Halten Sie einen Stapel von Kreisobjekte, arbeiten Sie sich durch eine sortierte Kopie des Arrays, erweitern den oberen Bereich oder einen neuen Bereich entsprechend hinzufügen. Genauer gesagt, wenn in dem Feld der Wert 1 + der Endwert für den Bereich Objekt auf der zu dem Stapel, für diesen Bereich den Endwert erhöht, wenn es eine neue Palette nicht schieben ist (mit start = end = Wert bei index in array) auf den Stapel.
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]]
Hier ist mein bester Schuss in Haskell.
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;
}
Python (> = 2.6)
Diese Version zusätzlich behandelt Duplikate und unsortiert Sequenzen.
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
Beispiel:
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])
Ausgabe:
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
