Problem:
Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.
Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.
Examples:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
Input: letters = ["c", "f", "j"] target = "a" Output: "c" Input: letters = ["c", "f", "j"] target = "c" Output: "f" Input: letters = ["c", "f", "j"] target = "d" Output: "f" Input: letters = ["c", "f", "j"] target = "g" Output: "j" Input: letters = ["c", "f", "j"] target = "j" Output: "c" Input: letters = ["c", "f", "j"] target = "k" Output: "c" |
Note:
lettershas a length in range[2, 10000].lettersconsists of lowercase letters, and contains at least 2 unique letters.targetis a lowercase letter.
Link: https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/
Idea:
- Scan the array Time complexity: O(n)
- Binary search Time complexity: O(logn)
Solution 1:
C++ / Scan
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua // Runtime: 16 ms class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { for (const char c : letters) if (c > target) return c; return letters.front(); } }; |
C++ / Set
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Runtime: 16 ms class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { vector<int> seen(26, 0); for (const char c : letters) seen[c - 'a'] = 1; while (true) { if (++target > 'z') target = 'a'; if (seen[target - 'a']) return target; } return ' '; } }; |
C++ / Binary Search
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Runtime: 15 ms class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { int l = 0; int r = letters.size(); while (l < r) { const int m = l + (r - l) / 2; if (letters[m] <= target) l = m + 1; else r = m; } return letters[l % letters.size()]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment