原問題網址:744. Find Smallest Letter Greater Than Target
問題描述
給定排序過後的 character array letters
,其中只有英文小寫字母。此外,給定一個目標字母 target
,欲求 array 中大於 target
的最小元素。
另外,letters 也會 wrap around。例如: target = 'z'
且 letters = ['a', 'b']
,則答案為 'a'
。
解題思路
- 因為只會包含英文小寫字母,可以利用一個長度 26 的 boolean array 紀錄
letters
中哪些字母出現過(一個 linear scan 可完成)。 - 接著從
target
字母對應的 index 的下一格開始尋找哪一個字母在letters
中出現過,即可找到大於target
的最小字母為何。 - 不過我當初在寫這題的時候沒注意到題目有提到「已排序」這個條件,這個解法只能達到 linear time。可見官方解答有更快的解法。
以下為用 C 語言實作的程式碼:
char nextGreatestLetter(char* letters, int lettersSize, char target){
bool has_character[26];
for (int i = 0; i < 26; i++) {
has_character[i] = false;
}
for (int i = 0; i < lettersSize; i++) {
has_character[letters[i] - 'a'] = true;
}
int next_greatest_letter_index = (target - 'a' + 1) % 26;
while (!has_character[next_greatest_letter_index]) {
next_greatest_letter_index = (next_greatest_letter_index + 1) % 26;
}
return 'a' + next_greatest_letter_index;
}