如果空間足夠大,可以定義一個大的數組a[qq号],初始為零然後.這個qq号登陸了
就a[qq号]
最後統計大于等于2的QQ号
這個用空間來代替時間
不成熟的想法
2w x 300s
所以用6000.000個桶。刪除超時的算法後面說,所以平均桶的大小是1
假設qq号碼一共有10^10個,所以每個桶裝的q号碼是10^10/(6*10~6)個,
這個是插入時候的最壞效率(插入同個桶的時候是順序查找插入位置的)
qq的節點結構和上面大家讨論的基本一樣,增加一個指針指
向輸出列表,後面說
struct QQstruct {
num_type qqnum,
timestamp last_logon_time,
QQstruct *pre,
QQstruct *next,
OutPutlist *out //用于free節點的時候,順便更新下輸出列表
}
另外增加兩個指針列表
第一個大小300的循環鍊表,自帶一個指向 QQStruct的域,循環存300秒内的qq指針。
時間一過就fee掉,所以保證所有桶占用的空闾在2wX30以内.
第二個是輸出列表,就是存放題目需要輸出的節點。
如果登陸的用戶,5分鐘内完全沒有重複的話,每秒free2w個節點
不過在free的時候,要判斷一下時間是不是真的超時,因為把節點入桶的時候,遇到重複的,
會更新一下最後登陸的時間。當然啦,這個時候,要把這個q号碼放到需要輸出的列表裡面
2020年更多、更全、更新大廠面試資料,歡迎 群學習交流,個人簡介信息加群領取
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!