这是悦乐书的第 306 次更新, 第 326 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 175 题 (顺位题号是 744). 给定一个仅包含小写字母的有序字符数组, 并给定目标字母目标, 找到数组中大于给定目标字符的最小元素. 例如, 如果目标是 target ='z'并且 letters = ['a','b'], 则答案是'a'. 例如:
输入: letters = ["c","f","j"],target ="a"
输出:"c"
输入: letters = ["c","f","j"],target ="c"
输出:"f"
输入: letters = ["c","f","j"],target ="d"
输出:"f"
输入: letters = ["c","f","j"],target ="g"
输出:"j"
输入: letters = ["c","f","j"],target ="j"
输出:"c"
输入: letters = ["c","f","j"],target ="k"
输出:"c"
注意:
数组的长度范围为 [2,10000].
数组中的字母由小写字母组成, 并包含至少 2 个唯一字母.
target 是一个小写字母.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
根据题目的意思和给出的示例, 如果数组中存在大于目标字母的最小元素, 就返回该元素, 不存在就返回数组第一个元素. 因为数组是已经排过序的, 可以直接使用循环来处理, 从前往后依次比较, 如果大于目标字母就返回当前元素, 不存在就返回数组第一个元素.
- public char nextGreatestLetter(char[] letters, char target) {
- for (int i=0; i<letters.length; i++) {
- if (letters[i]> target) {
- return letters[i];
- }
- }
- return letters[0];
- }
03 第二种解法
我们也可以使用二分法来查找, 定好起始点, 每次取中间位置的元素来进行比对, 如果中间位置元素大于目标字母, 就将终点往左移到中间位置, 反之要是中间位置元素小于等于目标字母, 就将起点右移到中间位置的右一位. 最后, 如果起点已经移动到终点了, 说明没有找到对应的元素, 返回数组第一个元素即可, 反之就返回起点所对应的元素.
- public char nextGreatestLetter2(char[] letters, char target) {
- int start = 0, end = letters.length;
- while (start <end) {
- int mid = (end+start)/2;
- if (letters[mid]> target) {
- end = mid;
- } else {
- start = mid+1;
- }
- }
- return start == letters.length ? letters[0] : letters[start];
- }
04 小结
算法专题目前已日更超过五个月, 算法题文章 175 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/12946eb39242