ETH官方钱包

前往
大廳
主題

LeetCode - 1854. Maximum Population Year 解題心得

Not In My Back Yard | 2022-09-19 12:00:01 | 巴幣 2 | 人氣 235

題目連結:


題目意譯:
你被給定一個二維整數陣列 logs,其中 logs[i] = [birthi, deathi] 代表第 i 個人的出生以及死亡年份。

年份 x 的人口數為該年活著的人之個數。如果 x 位於範圍 [birthi, deathi - 1] 之內(含端點)則第 i 個人將會被算進人口數中。注意到在某人死亡年份,他們是不算在該年人口數中的。

回傳最早有著最大人口數的年份。

限制:
1 ≦ logs.length ≦ 100
1950 ≦ birthi < deathi ≦ 2050



範例測資:
範例 1:
輸入: logs = [[1993,1999],[2000,2010]]
輸出: 1993
解釋: 最大人口數為 1,而且 1993 是最早有著這個人口數的。

範例 2:
輸入: logs = [[1950,1961],[1960,1971],[1970,1981]]
輸出: 1960
解釋:
最大人口數為 2,而且其發生於 1960 和 1970。
它們之中最早的年份為 1960。


解題思維:
可以看到年份的跨度才足足 101 年而已,而且 logs 的長度最大也僅僅只有 100。

因此我們可以直接窮舉所有年份(即從 1950 年開始),然後對每個年份去看這個年份落於 logs 中多少人的生死年份之間。然後取其中的最大值之發生年份,即可得到所求(如題目所述,多個最大人口數之年份則取最早的)。



如果題目的年份跨度變大了,而且 logs 的最大長度也變長的話,就需要類似這題的解法(即掃描線演算法(Sweep Line Algorithm))。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

追蹤 創作集

作者相關創作

更多創作