LeetCode每日一题:寻找比目标字母大的最小字母(744题)
题目描述
给定一个字符数组 letters,该数组按非递减顺序排序,以及一个字符 target。letters 里至少有两个不同的字符。返回 letters 中大于 target 的最小的字符。如果不存在这样的字符,则返回 letters 的第一个字符。
示例
示例 1:
输入: letters = ['c', 'f', 'j'],target = 'a'
输出: 'c'
解释:letters 中字典上比 'a' 大的最小字符是 'c'。
解题思路
由于 letters 是有序的,我们可以使用二分查找算法来高效地找到答案。二分查找可以帮助我们在 O(log n) 的时间复杂度内找到目标值。具体步骤如下:
- 初始化两个指针
l 和 r,分别指向数组的开始和结束。 - 当
l 小于 r 时,计算中间位置 mid。 - 如果
letters[mid] 小于等于 target,则将 l 移动到 mid + 1,否则将 r 移动到 mid。 - 最后,如果
letters[r] 大于 target,则返回 letters[r],否则返回 letters[0]。
代码实现
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
// letters 有序,可以二分查找
int l = 0, r = letters.size() - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (letters[mid] <= target) {
l = mid + 1;
} else {
r = mid;
}
}
if (letters[r] > target) {
return letters[r];
}
return letters[0];
}
};
总结
通过二分查找,我们可以高效地解决这个问题。这种方法不仅时间复杂度低,而且代码简洁易懂。在实际应用中,对于有序数据集,二分查找是一种非常有效的搜索方法。