수직선의 C# 구현
https://stackoverflow.com/questions/1614137
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);
line.CheckRange(10, 25);
NumberLine 수직선을 나타내는 클래스입니다.나는 그것에 다양한 숫자 범위를 표시하고 싶습니다.그만큼 CheckRange 메소드는 어느 부분을 반환해야합니까? 10-25 내가 표시한 것과 표시하지 않은 것.이 경우에는 다음을 반환해야 합니다. 10-20 표시가 되어 있지 않으며, 20-25 표시되어 있습니다.
o(n)을 수행하지 않는 효과적인 구현을 어떻게 구현할 수 있습니까?
감사합니다.
메모: 이것은 아니다 숙제.사용자 정의 데이터베이스 구현 트랜잭션에 이 정보가 필요합니다.프로그래밍을 배우고 있어요 홀로.
다른 팁
해시 세트를 사용하십시오u003CT> :
public class NumberLine : HashSet<int>
{
public void AddRange(int start, int end)
{
int count = (end-start)+1;
UnionWith(Enumerable.Range(start, count));
}
public IEnumerable<int> CheckRange(int start, int end)
{
NumberLine other = new NumberLine();
other.AddRange(start, end);
other.IntersectWith(this); // marked
// other.ExceptWith(this); // not marked
return other;
}
}
CheckRange에서 무엇을 반환하고 싶은지 확실하지 않거나 문자열을 인쇄하려는 경우. 지정한 범위와 같은 간단한 것을 위해서는 다음을 사용할 수 있습니다.
public string CheckRange(int start, int end)
{
NumberLine other = new NumberLine();
other.AddRange(start, end);
IEnumerable<int> marked = other.Intersect(this);
IEnumerable<int> notMarked = other.Except(this);
int markedMin = marked.Min();
int markedMax = marked.Max();
int notMarkedMin = notMarked.Min();
int notMarkedMax = notMarked.Max();
string markedString = (markedMin == markedMax)
? markedMin.ToString()
: string.Format("{0} - {1}", markedMin, markedMax);
string notMarkedString = (notMarkedMin == notMarkedMax)
? notMarkedMin.ToString()
: string.Format("{0} - {1}", notMarkedMin, notMarkedMax);
return string.Format("Marked: {0}\r\nNot Marked: {1}", markedString, notMarkedString);
}
다음과 같은 분할 범위를 처리하지 않습니다.
Marked: 10-15, 20-25
Not Marked: 16-19
그러나 그것은 당신을 올바른 길로 데려 가야합니다.
좋아, 당신이 어디로 가는지 봅니다.
루센 이것은 매우 큰 비트 필드로 수행합니다.
가능한 숫자 범위가 1에서 64로 고정되어 있다고 가정하면,이 숫자 각각은 64 비트 int의 해당 위치의 비트에 해당합니다. (NO 1은 비트 0이고 2는 비트 1입니다).
범위에 숫자를 추가하면 해당 비트를 켜십시오 (예에서는 비트 0에서 4 및 19 ~ 29에서 29까지 켜집니다).
이제 다양한 숫자를 확인하려면 해당 비트 범위가 켜져있는 또 다른 64 비트 int를 생성하고 두 비트 필드에서 비트와 (&)를 수행합니다. 결과의 1 비트는 겹치는 범위입니다.
64보다 더 많은 숫자의 경우 비트 수를 확장하십시오 (아마도 배열 또는 정수 목록으로 작업하여)
도움이 되었기를 바랍니다 :)
업데이트: 확장 성
64 비트 아키텍처를 작업하고 단일 작업에서 64 비트 정수를 사용할 수 있다고 가정 해 봅시다. 이상적으로는 64 비트 int를 사용합니다.
이제 가능한 숫자 범위가 1에서 64,000으로 실행된다고 가정 해 봅시다. 이는 1000 64 비트 int가 필요합니다.
이제 몇 가지 사용 사례를 살펴 보겠습니다
70-80의 범위를 확인하고 싶습니다. 이렇게하려면 수표를 위해 1000 개의 int가 필요하지 않으며, 하나만 int 만 필요하지 않으며, 우리는 배열의 두 번째 요소에 대해 확인하고 있음을 알고 있습니다.
나는 2000-10,000의 범위를 다시 확인하고 싶다. 우리는 하나의 int 만 필요하고, 배열 31S에서 위치를 계산하고 (생각한다) 비트를 설정하고 비교한다. 그런 다음 10,000 명 (156?)을 때릴 때까지 목록을 반복하고, 길을 따라 비교하고, 반환 할 정수 목록을 작성합니다.
업데이트 2: 그것은 O (1)가 아닙니다.
확인할 범위의 크기에 따라 O (1)로이를 구현할 수 있습니다.
그러나이 알고리즘을 사용하여 일반적인 경우는 여전히 O (n)입니다.
NumberLine 내에 범위 자체를 저장하면 어떨까요?겹치는 범위가 추가되면 병합을 수행할 수 있습니다.그런 다음 CheckRange는 개별 요소 대신 NumberLine 내부에 저장된 범위를 쿼리할 수 있습니다.그러면 요소 수의 O(N) 대신 범위 수의 O(N)이 됩니다.가능하면 범위를 병합하면 범위 수가 AddRange에 대한 호출 수보다 작아집니다.
아래 코드 샘플을 참조하세요.저는 .Net 컬렉션 전문가가 아니므로 더 나은 컬렉션 유형을 선택하면 보다 효율적인 구현이 가능할 수도 있습니다. _NT 트리 구조에 값을 저장할 것을 제안했습니다.이를 범위에도 적용하고 시작 번호로 저장할 수 있습니다.이렇게 하면 추가하고 확인할 때 범위를 더 빠르게 검색할 수 있습니다.현재 구현에서는 범위를 끝에 추가하는 것이 처음에 범위를 추가하는 것보다 느립니다.이를 효율적인 트리에 저장하면 범위 수에서 복잡성이 O(log N)이 됩니다.
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
namespace NumberLine
{
class Program
{
static void Main(string[] args)
{
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(10, 12);
line.AddRange(20, 30);
List<Range> ranges = line.CheckRange(10, 25);
foreach (Range r in ranges)
{
for (int i = r.Start; i <= r.End; i++)
{
Console.WriteLine(i);
}
}
}
}
class Range
{
public int Start;
public int End;
}
class NumberLine
{
private SortedList<int, Range> Ranges = new SortedList<int, Range>();
public void AddRange(int start, int end)
{
if (Ranges.Count == 0)
{
Ranges.Add(start, new Range() { Start = start, End = end });
}
else
{
foreach (Range currentRange in Ranges.Values)
{
if (start <= currentRange.Start)
{
if (end >= currentRange.End)
{
currentRange.Start = start;
currentRange.End = end;
}
else
{
currentRange.Start = start;
}
Ranges.RemoveAt(start);
Ranges.Add(start, currentRange);
break;
}
else
{
if (start <= currentRange.End)
{
currentRange.End = end;
break;
}
else
{
Ranges.Add(start, new Range(){ Start = start, End = end });
break;
}
}
}
}
}
public List<Range> CheckRange(int start, int end)
{
List<Range> result = new List<Range>();
foreach (Range currentRange in Ranges.Values)
{
if (start <= currentRange.End)
{
if (end <= currentRange.End)
{
result.Add(new Range() { Start = currentRange.Start, End = end });
break;
}
else
{
if (start <= currentRange.Start)
{
result.Add(new Range() { Start = currentRange.Start, End = currentRange.End });
}
else
{
result.Add(new Range() { Start = start, End = currentRange.End });
}
}
}
}
return result;
}
}
}
o (n)은 요소의 수가 다르므로 O (1)은 일정한 시간을 의미합니다.
나는 이것을 구현하는 O (1) 방법을 생각할 수 없습니다.
앱의 세부 사항에 대해서는 잘 모르겠지만 직관은 설정 기반 작업이기 때문에 데이터베이스에서 훨씬 더 잘 처리 될 것이라고 말합니다.
즉
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
이 문제를 반복적으로 해결하려고하면 도움이 될 수 있습니다. 예를 들어 Linenumber 클래스를 범위 목록으로로드하면 해당 범위에는 시작 및 종료 int가 있습니다. 그런 다음 'CheckRange (a, b)'메소드 대신 a 'hasnumber (a)'메소드를 구현하십시오. 범위 목록을 반복하여 간단히 수행하고 메소드 'Isinrange (a)를 범위 클래스에서 호출하여 데이터 모델이 다음과 같습니다.
LineNumber {
List<Range> ranges;
aadRange(a,b);
// Loops through all ranges and calls isInRange on each method
isInRange(a);
//just iterates over isInRange from a to b
checkRange(a,b)
}
Range {
Range(a,b)
isInRange(a);
}
이렇게하면 작업 코드와 인터페이스가 제공됩니다. 충분히 빠르지는 않지만 아직 알지 못합니다. 나중에 루센 구현을 남겨 두십시오. :)
이것은 완전한 솔루션이 아니지만 다른 접근 방식은 더 나은 결과를 얻는 데 도움이 될 수 있습니다.
