날짜의 차이를 찾으세요?

Question

나는 많은 이벤트가 예정되어 있고, 10 일 내에 이벤트가 일어나지 않는 나의 스케줄 된 이벤트에 10 일 간격이 있는지 확인하고 싶다. 10 일 간격을 찾기 위해 좋은 데이터 구조와 검색 알고리즘이 있습니까?

Answer 1

효율성, 메모리 사용 등을 신경 쓰는지 여부에 달려 있습니다. 다른 모든 방법이 실패하면 O (n * log (n)) 알고리즘을 사용하여 날짜별로 정렬하고 각 날짜 쌍의 차이를 가져올 수 있습니다.

편집 : 지금 당신의 문제를 더 잘 이해하고 있다고 생각하십시오. 두 가지 옵션 : 1) 날짜가 정렬되어 있다고 가정하면 두 개 사이의 증가분이 < 인 경우 이진 검색이 중지됩니다. 아마도 더 큰 날짜 범위를 갖는 하위 배열을 우선적으로 검색 할 수 있습니다. 이것은 로그 n과 n 사이의 어딘가에 해당합니다. 2) 이전 날짜 또는 다음 날짜와의 차이점을 날짜와 함께 저장합니다. 우선 순위 대기열을 사용하여 이전 또는 다음 날짜와의 차이로 정렬되도록하십시오. 일정 시간의 최대 차이로 날짜를 표시 할 수 있습니다.

Answer 2

나는 이벤트를 저장하기 위해 정렬 된 링크 된 목록을 사용하고 적어도 다음 10 일보다 빠른 해시 테이블 (키 : 이벤트 날짜)에 이벤트를 저장합니다. 연결된 목록에 새 이벤트를 삽입 할 때 새 이벤트와 이웃 사이의 날짜 차이를 확인해야합니다. 최대 해시 테이블을 수정하십시오.

편집 :

어쩌면 여분의 해시 테이블을 만들기위한 필요가 없습니다. 목록 항목이처럼 보이는 특별 주문한 연결된 목록을 작성 :

[EVENTDATE | nextEventPointer | next10DayEventPointer | previous10DayEventPointer] 다음 이벤트에

next10DayEventPointer 포인트되는 최소한 10 일전 다음에 비해 하나. previous10DayEventPointer는 이전 이벤트를 가리키며, 다음 이벤트보다 적어도 10 일 이른 것입니다.

HEAD 항목 next10DayEventPointer는 적어도 다음 이벤트보다 먼저 시작하는 첫 번째 이벤트를 가리 킵니다. HEAD 항목 previous10DayEventPointer가 NULL입니다.

10Day 이벤트는 next10DayEventPointer를 사용하여 HEAD에서 시작할 수 있습니다.

삽입하는 동안 필요한 경우 포인터를 업데이트해야합니다.

편집 :이 같은

사용 이진 검색 :

class Program 
{ 
    static void Main(string[] args) 
    { 
     Dictionary<int, int> result = new Dictionary<int, int>(); 
     int [] dates = {2, 2, 2, 2, 2, 7,18, 19, 23, 33, 34, 35, 50, 70}; 

     IsThereIntervalXBetween(dates, 10, 0, dates.Length - 1, result); 
     foreach (var key in result.Keys) 
      Console.WriteLine("Index:{0} Date:{1} Next:{2}",key,dates[key],dates[key+1]); 
    } 

    static void IsThereIntervalXBetween(int[] dates, int interval, int firstIndex, int lastIndex, Dictionary<int, int> result) 
    { 
     if (lastIndex - firstIndex == 1) 
     { 
      result.Add(firstIndex, dates[firstIndex]); 
      return; 
     } 

     int middleIndex = (firstIndex + lastIndex)/2; 

     if (dates[middleIndex] - dates[firstIndex] >= interval) 
      IsThereIntervalXBetween(dates, interval, firstIndex, middleIndex, result); 


     if (dates[lastIndex] - dates[middleIndex] >= interval) 
      IsThereIntervalXBetween(dates, interval, middleIndex, lastIndex, result); 
    } 
} 

이것은 바람직하지 않다, 재귀,하지만 여전히 비 재귀로 변환하기 쉽습니다.

Answer 3

u는 일정을 저장하기 위해 링크 된 목록을 정렬 할 수 있으며 연결된 목록 노드 주소의 주소로 키와 값으로 날짜가 포함 된 해시 맵에 동일한 항목을 저장할 수 있습니다. 그래서 검색하고 u가 일정에 대한 10 일 시간을 o (1) 시간에 넣고 최대 o (n) 시간에 일정을 삽입하는지 확인하십시오.