題目連結:
題目意譯:
給定一個已排序的字元列表 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 中第一個字母即可(因為字母頭尾相接)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。