題目連結(jié):
題目意譯:
你被給定一個(gè)索引值從 0 開始數(shù)的二維字串陣列 access_times,其大小為 n。對(duì)於每一個(gè) i 值,其中 0 ≦ i ≦ n - 1,access_times[i][0] 代表著一位員工的名字而 access_times[i][1] 代表著該員工的存取時(shí)間。access_times 中所有項(xiàng)目都發(fā)生在同一天。
存取時(shí)間是以二十四小時(shí)制的四位數(shù)字表示,例如說(shuō) "0800" 或是 "2250"。
一位員工如果是「高存取量」的,代表著他在某一個(gè)小時(shí)內(nèi)存取了系統(tǒng)三次或更多次。
存取時(shí)間恰好差一小時(shí)的不算是同一個(gè)小時(shí)內(nèi)的存取次數(shù)。例如說(shuō),"0815" 和 "0915" 不能算作是同一個(gè)小時(shí)的存取次數(shù)。
位於一天的開頭和結(jié)尾的存取時(shí)間不能算在同一個(gè)小時(shí)內(nèi)。例如說(shuō),"0005" 和 "2350" 不是同一個(gè)小時(shí)內(nèi)的。
回傳一個(gè)包含著所有高存取量的員工之名字,順序任意。
限制:
1 ≦ access_times.length ≦ 100
access_times[i].length == 2
1 ≦ access_times[i][0].length ≦ 10
access_times[i][0] 只由小寫英文字母組成。
access_times[i][1].length == 4
access_times[i][1] 是二十四小時(shí)制。
access_times[i][1] 只由 '0' 到 '9' 組成。
範(fàn)例測(cè)資:
範(fàn)例 1:
輸入: access_times = [["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]
輸出: ["a"]
解釋: "a" 在 [05:32, 06:31] 這一小時(shí)間有三次存取,其為 05:32 、 05:49 和 06:21。
但 "b" 連超過(guò)兩次存取都沒(méi)有。
所以答案為 ["a"]。
範(fàn)例 2:
輸入: access_times = [["d","0002"],["c","0808"],["c","0829"],["e","0215"],["d","1508"],["d","1444"],["d","1410"],["c","0809"]]
輸出: ["c","d"]
解釋: "c" 在 [08:08, 09:07] 這一小時(shí)間有三次存取,其為 08:08 、 08:09 和 08:29。
"d" 在 [14:10, 15:09] 這一小時(shí)間也有三次存取,其為 14:10 、 14:44 和 15:08。
不過(guò),"e" 只有一次存取次數(shù)。所以它不會(huì)在答案裡,因此最終答案為 ["c","d"]。
範(fàn)例 3:
輸入: access_times = [["cd","1025"],["ab","1025"],["cd","1046"],["cd","1055"],["ab","1124"],["ab","1120"]]
輸出: ["ab","cd"]
解釋: "ab" 在 [10:25, 11:24] 這一小時(shí)間有三次存取,其為 10:25 、 11:20 和 11:24。
"cd" 在 [10:25, 11:24] 這一小時(shí)間也有三次存取,其為 10:25 、 10:46 和 10:55。
所以答案為 ["ab","cd"]。
解題思維:
先把同一個(gè)員工的存取次數(shù)之時(shí)間抓出來(lái)(可以用雜湊表(Hash Table),也可以將 access_times 根據(jù)名字來(lái)排序)。
然後將同一個(gè)員工的存取時(shí)間排序。而因?yàn)?access_times 最大也才 100,因此不需要什麼滑動(dòng)視窗(Sliding Window)的技巧,直接窮舉每一個(gè)存取時(shí)間當(dāng)作該小時(shí)的「開頭」,然後檢查有多少其他的存取時(shí)間落在其中即可。
最後把有符合條件的員工名字抓出來(lái)存在一個(gè)列表中回傳即可。
此次分享到此為止,如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方,也煩請(qǐng)各位大大撥冗討論。