數據結構訪問

給定特定網站所有用戶的登錄/註銷時間，格式爲：（userId，登錄時間，註銷時間）。存儲這些數據，以查詢在給定時間範圍內登錄和註銷的用戶總數。數據結構訪問

我應該使用哪種數據結構？以及如何實施它？

2016-06-07 James

一個天真的解決方案將是以下。讓數據按'loginTime'排序，並按照'logoutTime'排序數據的一個副本。要計算在A和B之間登錄並在C和D之間註銷的用戶，首先計算在A和B之間登錄的用戶S，然後計算在C和D之間登出的用戶T.返回S和T的交集。 – blazs

在採訪中，解決方案可能不是唯一重要的事情。您還需要通過提出問題來證明您的想法，從而完善這一點。您需要多少數據才能做到這一點可能是最重要的，因爲它會對良好的解決方案產生嚴重影響。數據的特徵 - 單個用戶的估計用戶數量/登錄/註銷頻率也影響良好的解決方案。 – moreON

可能你可以查看boost庫的多索引容器嗎？ – DAG

如果你想在程序中做到這一點：

只需創建包含類用戶類型變量的簡單數組。

用戶類應該具有屬性：userId，loginTime，logoutTime。

檢查用戶的總數誰登錄並在給定的時間範圍內退出將是這樣的：

for (user in userArray) 
    if (user.loginTime > inputLoginTime && user.logoutTime < inputLogoutTime) 
    count++;

您可以檢查用戶在O（n）的時間總數。

如果你想在服務器上做到這一點，例如。 MySQL的。

創建一個表格userId，loginTime，logoutTime作爲列的用戶。

SELECT COUNT(*) FROM User WHERE User.loginTime > inputLoginTime AND User.logoutTime < inputLogoutTime;

2016-06-07 07:16:04 seokhoonlee

我不認爲有任何單一的數據結構，這將使你比下面提到的方法更好的複雜性： - 用於註銷次

2016-06-07 07:24:37 ravi

對於第2點不幸的是，用戶總數與登錄總次數（和註銷）略有不同，如果單個用戶多次登錄和登出，他們仍然是單個用戶。我不認爲會有避免掃描整個範圍來過濾掉重複用戶的好方法。 – moreON

你要找的數據結構被稱爲interval tree，它基本上有一個像與間隔的開始格式的二進制搜索樹（登錄時間）作爲值（按照BST排序）。

這DS具有如下的時間複雜性：

2016-06-07 08:42:20

回答