정수 배열을 범위 집합으로 어떻게 표시합니까?(연산)
https://stackoverflow.com/questions/117691
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
정수 배열이 주어지면 이를 반복하고 그것이 포함하는 모든 범위를 파악하는 가장 간단한 방법은 무엇입니까?예를 들어 다음과 같은 배열의 경우:
$numbers = array(1,3,4,5,6,8,11,12,14,15,16);
범위는 다음과 같습니다.
1,3-6,8,11-12,14-16
해결책
배열이 오름차순으로 정렬되면 문제는 쉽습니다.정의하다 Range 시작과 끝이 있는 구조 또는 클래스.그런 다음 배열을 살펴보십시오.현재 요소가 이전 요소보다 하나 더 많은 경우 업데이트 Range.end, 그렇지 않으면 이 요소를 사용하여 새 범위를 만듭니다. Range.begin.범위를 동적 배열이나 연결 목록에 저장합니다.아니면 그냥 가면서 인쇄해 보세요.
배열이 정렬되지 않을 경우 먼저 정렬하십시오.
다른 팁
이를 수행하는 C# 3.0'y 방법은 다음과 같습니다.
가볼만한 곳:
- 자동 속성(public int Property { get;세트;})
- 새로운 객체 이니셜라이저 사용(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;
}
}
건배, 데이비드
다음은 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
나도 알아, 나도 알아, 그건 아닌데 연산, 하지만 단순히 솔루션을 구현하는 것보다 들여쓰기 문제 없이 실제로 설명하는 것이 더 어렵다는 것을 알았습니다.
첫 번째:두 번째 정렬 :그런 다음 토 케이즈 :첫 번째 값을 인쇄하고 다음 값을 반복합니다.'현재' 값이 마지막 값 +1과 같으면 건너뜁니다.그렇지 않고 값을 건너뛴 경우 대시와 값을 인쇄하고, 그렇지 않으면 쉼표를 인쇄하고 반복하세요.
그래야 합니다.내가 당신의 숙제를 코딩해 주기를 원하지 않는 한?:)
귀하의 예에서와 같이 배열이 정렬되면 최소값과 최대값이 포함된 버킷을 정의합니다.
초기화:최소값과 최대값이 첫 번째 값과 동일한 버킷을 생성합니다.
고리:각 값을 현재 버킷의 최대값과 비교합니다.현재 최대값과 같거나 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>
기본적으로 각 항목의 목록(버킷에서 가장 낮은 항목, 버킷에서 가장 높은 항목)으로 끝납니다.이것이 당신의 범위입니다.
목록이 아직 정렬되지 않은 경우 먼저 정렬하세요.
C(gcc)
그것은 비슷하다 파이썬 버전.
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
목록이 순서대로 정렬되어 있다고 가정하면 끝에서 시작하여 다음 항목을 계속 뺄 수 있습니다.차이는 1이지만 범위 내에 있습니다.그렇지 않은 경우 새 범위를 시작합니다.
즉
16-15 = 1
15-14 = 1
14-12 = 2, 범위는 16-14 - 새 범위를 시작합니다.
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
}
}
내 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 = [ $_ ];
}
}
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]
안녕하세요, GHad
나는 1.5 릴리스에서 Subversion에 도입된 mergeinfo 속성이 당신이 요구하는 것과 동일한 형식을 가지고 있다고 생각합니다. 따라서 잠재적으로 Subversion의 소스를 조사하여 어떻게 하는지 알아낼 수 있습니다.여기에 이미 게시된 다른 제안과 다른 점이 있으면 놀랄 것입니다.
배열 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()
글쎄, 난 그렇게 할 거야.
범위 값의 시작/끝을 포함하는 간단한 범위 유형을 만듭니다.하나의 값만 취하고 start = end = value를 설정하는 생성자를 추가합니다.범위 개체의 스택을 유지 관리하고, 배열의 정렬된 복사본을 통해 작업하고, 최상위 범위를 확장하거나 적절하게 새 범위를 추가합니다.더 구체적으로 말하면, 배열의 값이 1 + 스택에 있는 범위 개체의 끝 값인 경우 해당 범위의 끝 값을 늘리고, 그렇지 않은 경우 새 범위를 푸시합니다(시작 = 끝 = 값 배열의 인덱스)를 스택에 추가합니다.
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에서 내 최고의 샷은 다음과 같습니다.
펄 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;
}
파이썬(>= 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
