APP下载

LeetCode基础演算法题第142篇:找到阵列中大于目标字母的最小字母

消息来源:baojiabao.com 作者: 发布时间:2024-05-11

报价宝综合消息LeetCode基础演算法题第142篇:找到阵列中大于目标字母的最小字母

技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后> 到中级难度,最后到hard难度全部完。目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和> 精力有限,其他语言的实现有兴趣的朋友请自己尝试。初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分散式> 聊到大资料框架,从大资料聊到人工智能,... ...。

如果有任何问题可以在文章后评论或者私信给我。

持续分享,敬请关注。

LeetCode 744. 找到大于目标的最小字母(Find Smallest Letter Greater Than Target)

问题描述:

给定一个已排序的仅包含一个个小写字母的列表letters,给定一个目标字母target,请在letters中找到大于target的最小字母。允许循环查询,

例如,如果目标target = 'z',letters = ['a', 'b'],答案是'a'。

注:

letters的长度区间为[2, 10000];letters 由小写字母组成,并至少包含2个不同字母;target 是一个小写字母;

示例:

C语言实现:

一看到"已排序"就开心了。

因为有序所以我们通过二分查询算法来实现。

根据二分查询算法的原理,我们定义三个变数left,right和mid,分别初始化为0,阵列长度,阵列长度的一半;临界条件我们定为 left我们要找的是比target大一点的字母,所以当target大于等于阵列中的当前元素时,说明我们要找的元素在当前元素的右边;否则就在当前元素的左边。

我们不断的缩小查询范围。当跳出循环时,会出现下面两种情况:

位于下标left处的元素大于targe,那么返回left处的元素。例如letters=[e,f,g], target = a;位于下标left处的元素小于等于targe,那么返回left+1处的元素。例如letters=[e,f,g], target = e;此外我们还要考虑一种特殊情况,即如果target大于等于letters中的最大元素,即最后一个元素,那么返回letters[0]。

所以最终的程式码如下:

Java语言实现:

Java 的实现和C语言的实现一致,不再撰述。程式码如下:

Python语言实现:

Python 的实现和C语言的实现一致,不再撰述。程式码如下:

谢谢大家一直以来的关注和支援!

我一直在努力的写好每一篇文章,画好每一份插图。但是作为一个996从业人员,时间精力十分有限。所以针对评论部分,以后只回答粉丝的问题和私信。希望仅仅是路过的朋友能够体谅,希望更多人关注《吾是我师》,谢谢!

2019-07-18 10:54:00

相关文章