找到日期的區別？

我有一堆事件是預定的，我想檢查是否有10天的時間間隔在我的預定活動中，在那10天內沒有發生任何事件。有好的數據結構和搜索算法來找到10天的時間間隔嗎？找到日期的區別？

2013-02-27 John Walk

取決於您是否關心效率，內存使用情況等。如果一切都失敗了，您可以使用O（n * log（n））算法按日期排序並獲取每個連續日期對之間的差異。

編輯：認爲我現在更好地理解你的問題。兩個選項： 1）假設日期排序，二進制搜索它們停止時，他們之間的增量是< 10.也許你可以優先搜索具有較大日期範圍的子陣列。這介於log n和n之間。 2）從日期或下一個日期與日期存儲差異。使用優先級隊列來保存它們與前一個或下一個日期的差異。您可以在恆定時間內以最大差異彈出日期。

來源

2013-02-27 16:44:51 nickd717

我需要登錄運行時效率，而不是空間 – 2013-02-27 16:46:24

是的，這是一個相當明顯的和非最佳的建議回顧。你認爲這項任務很普遍嗎？確定一些浪費的方法來跟蹤所有日期之間的時間間隔，從而可以基本查明O（n）時間內是否存在10天的間隔。 – nickd717 2013-02-27 16:56:17

我需要logn算法 – 2013-02-27 17:02:34

我會使用有序的鏈表來存儲事件，並且我會將事件存儲在散列表（鍵：事件日期）中，這些散列表至少比下一個表早10天。當您將新事件插入鏈接列表時，您必須檢查新事件與其鄰居之間的日期差異。最多修改哈希表。

編輯：

也許沒有必要創建一個額外的哈希表。創建一個特殊的有序鏈接列表，該列表項看起來像這樣：

[EVENTDATE | nextEventPointer | next10DayEventPointer | previous10DayEventPointer]

next10DayEventPointer點到下一個事件，這比下早至少10天一。 previous10DayEventPointer指向前一個事件，該事件至少比下一個事件晚10天。

HEAD項目next10DayEventPointer指向至少比下一個更早的第一個事件。 HEAD項目previous10DayEventPointer爲NULL。

您可以使用next10DayEventPointer查詢10天開始的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); 
    } 
}

這是遞歸的，這是不可取的，但還是很容易轉換成非遞歸。

來源

2013-02-27 16:52:24 boli

好吧，當我在哈希表中插入事件時，如果在10天內有兩個事件，我不能插入一個事件，我如何找到下一個可用的10天空插槽在logn中插入事件？你算法似乎O（n） – 2013-02-27 17:01:33

我想你誤解了這個問題，我有事件安排。我們假設這些是事件日期，3 5 8 10 12 14 15 19 23 33 34 39 40 45，你會發現有10天的間隔（23-33）。我想在logn中找到該時間間隔 – 2013-02-27 17:28:25

在這種情況下，您可以使用二分搜索樹。 http://en.wikipedia.org/wiki/Binary_search_tree每個節點都有兩個子節點，左側的子節點小於父節點，右側的子節點大於父節點。 – boli 2013-02-27 18:01:09

您可以對鏈表進行排序以存儲排定，並將其存儲在散列映射中，其日期作爲鍵和值作爲鏈接列表節點地址的地址。因此，要搜索並查看你是否有10天的時間來安排它的o（1）時間，並且插入一個時間表爲最大o（n）時間。

來源

2013-02-27 17:17:24 rohitmb

找到日期的區別？

回答

相關問題