題目：

官網題目連結

根據題目敘述，會給一個鍵為 N，值為 K 的非空陣列 A。其中 N 表示秒數，K 表示位置，也就是第 N 秒時會有樹葉掉落到位置 K 上。

題目還會給一個整數 X 表示終點，你必須找出最少第幾秒時 1~X 的位置上都會有落葉。

例如輸入 A=[1, 3, 1, 4, 2, 3, 5, 4]， X=5。
最少在第 6 秒時會有樹葉掉落到位置 5，且位置 1~5 都有樹葉，所以答案為 6。

如果 1~X 永遠不可能都有樹葉的話，你必須回傳 -1。

  • N 是範圍 [1~100000] 的整數。
  • 陣列 A 裡的所有元素都是範圍 [1~X] 的整數

解法：

這題不像 PermMissingElem 一樣可以用等差數列去減，因為樹葉掉落的位置可能會出現重複的，所以始終是必須記錄走過的不重複合法位置有哪些，空間複雜度最低只能 O(N)。

而由於我們有紀錄走過的不重複合法位置，所以可以得知當你剛好找到第 X 個不重複合法值時，他的時間就會是答案，總共只需遍歷一次。

  • 時間複雜度 O(N)
  • 空間複雜度 O(N)

PHP 程式碼：