Description
設計一個地鐵系統，支援三個操作：
checkIn(id, stationName, t): 乘客 id 在時間 t 從 stationName 進站checkOut(id, stationName, t): 乘客 id 在時間 t 從 stationName 出站getAverageTime(startStation, endStation): 回傳從 startStation 到 endStation 的平均旅行時間
Example:
Input: checkIn(45, “Leyton”, 3) -> checkOut(45, “Waterloo”, 15) -> getAverageTime(“Leyton”, “Waterloo”) Output: 12.0
Intuition#
核心思路：用一個 HashMap 記錄進站中的乘客（id -> (station, time)），另一個 HashMap 記錄每條路線的累計時間和次數（route -> (totalTime, count)）。
checkIn：記錄乘客的進站資訊checkOut：查找乘客的進站資訊，計算旅行時間，累加到對應路線getAverageTime：查找路線的累計時間 / 次數
Approaches#
1: Two HashMaps (Basic)#
- 概念: 直接用兩個 HashMap 儲存
- 時間複雜度: 每個操作
O(1)平均 - 空間複雜度:
O(n + r)- n 為進站中的乘客數，r 為路線數
class UndergroundSystem() {
// id -> (stationName, time)
private val checkIns = HashMap<Int, Pair<String, Int>>()
// "start->end" -> (totalTime, count)
private val routeData = HashMap<String, Pair<Double, Int>>()
fun checkIn(id: Int, stationName: String, t: Int) {
checkIns[id] = Pair(stationName, t)
}
fun checkOut(id: Int, stationName: String, t: Int) {
val (startStation, startTime) = checkIns.remove(id)!!
val route = "$startStation->$stationName"
val (totalTime, count) = routeData.getOrDefault(route, Pair(0.0, 0))
routeData[route] = Pair(totalTime + (t - startTime), count + 1)
}
fun getAverageTime(startStation: String, endStation: String): Double {
val route = "$startStation->$endStation"
val (totalTime, count) = routeData[route]!!
return totalTime / count
}
}⭐2: Two HashMaps (Data Class)#
- 概念: 使用自定義資料類別使程式碼更清晰可讀
- 時間複雜度: 每個操作
O(1)平均 - 空間複雜度:
O(n + r)- n 為進站中的乘客數，r 為路線數
class UndergroundSystem() {
private data class CheckIn(val station: String, val time: Int)
private data class RouteStats(var totalTime: Long = 0, var count: Int = 0) {
fun average(): Double = totalTime.toDouble() / count
}
private val checkIns = HashMap<Int, CheckIn>()
private val routeStats = HashMap<String, RouteStats>()
fun checkIn(id: Int, stationName: String, t: Int) {
checkIns[id] = CheckIn(stationName, t)
}
fun checkOut(id: Int, stationName: String, t: Int) {
val checkIn = checkIns.remove(id)!!
val route = "${checkIn.station}->$stationName"
val stats = routeStats.getOrPut(route) { RouteStats() }
stats.totalTime += t - checkIn.time
stats.count++
}
fun getAverageTime(startStation: String, endStation: String): Double {
return routeStats["$startStation->$endStation"]!!.average()
}
}🔑 Takeaways#
- Pattern: 聚合統計系統設計 -> HashMap 記錄進行中狀態 + HashMap 記錄累計統計
- 關鍵技巧: 路線用
"start->end"字串作為 key 簡單有效；用getOrPut簡化首次插入邏輯；Data Class 讓程式碼更具可讀性