Given a list of sorted array containing only lowercase letters, and a target letter, your task is to find the smallest letter in the list that is greater than the target. Also, you would need to wrap the result – if the target is ‘z’ and in the sorted array [‘a’, ‘b’], the answer is ‘a’.
Linear Scan
As the letters are already sorted, we ca do a O(N) linear scan until the smallest element found that is larger than the target.
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { for (const auto &n: letters) { if (n > target) { return n; } } return letters[0]; } }; |
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
for (const auto &n: letters) {
if (n > target) {
return n;
}
}
return letters[0];
}
};Binary Search
The sorted array makes it possible to do a binary search algorithm. The complexity is O(nlogn) where n is the size of the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { int lo = 0, hi = letters.size(); while (lo < hi) { int mi = lo + (hi - lo) / 2; if (letters[mi] <= target) { lo = mi + 1; } else { hi = mi; } } return letters[lo % letters.size()]; } }; |
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int lo = 0, hi = letters.size();
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (letters[mi] <= target) {
lo = mi + 1;
} else {
hi = mi;
}
}
return letters[lo % letters.size()];
}
};Record Last Position
We can use a set or a static array of size 26 to record if a lowercase letter has appeared in the list. Then we can start from the target and move the index one by one towards to the right (close-wise, wrap it to the front) until we found another recorded letter.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { bool data[26] = { false }; for (const auto &n: letters) { data[n - 97] = true; } target -= 97; do { target = (target + 1) % 26; } while (!data[target]); return static_cast<char>(97 + target); } }; |
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
bool data[26] = { false };
for (const auto &n: letters) {
data[n - 97] = true;
}
target -= 97;
do {
target = (target + 1) % 26;
} while (!data[target]);
return static_cast<char>(97 + target);
}
};–EOF (The Ultimate Computing & Technology Blog) —
Last Post: How to Solve Adsense Ads Showing Blank Yellow Block By Adding the Site to the Verified List
Next Post: Parity Sorting the Array by Index