主題

LeetCode - 744. Find Smallest Letter Greater Than Target 解題心得

Not In My Back Yard | 2021-01-05 00:00:07 | 巴幣 0 | 人氣 41

題目連結:


題目意譯:
給定一個已排序的字元列表 letters 其只包含小寫字母,再給定一目標字母 target,找到列表中最小的元素其大於給定的目標字母。

字母是頭尾相接的。例如,如果目標 target = 'z' 且 letters = ['a', 'b'],則答案為 'a'。

注:
letters 之長度介於範圍 [2, 10000] 之間。
letters 由小寫字母組成,且包含至少兩個相異字母。
target 是一個小寫字母。



範例測資:
輸入: letters = ["c", "f", "j"] 、 target = "a"
輸出: "c"

輸入: letters = ["c", "f", "j"] 、 target = "c"
輸出: "f"

輸入: letters = ["c", "f", "j"] 、 target = "d"
輸出: "f"

輸入: letters = ["c", "f", "j"] 、 target = "g"
輸出: "j"

輸入: letters = ["c", "f", "j"] 、 target = "j"
輸出: "c"

輸入: letters = ["c", "f", "j"] 、 target = "k"
輸出: "c"


解題思維:
先根據字典序,利用二分搜尋法(Binary Search)去找到第一個 letters 中大於 target 的字母(二分搜尋的作法可以參見這題)。

如果真的有找到,則就直接回傳該字母;反之,就回傳 letters 中第一個字母即可(因為字母頭尾相接)。




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

創作回應

更多創作