744. Find Smallest Letter Greater Than Target（python+cpp）

题目：

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:

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:
letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

解释：
第一反应是先排序在二分查找是怎么回事？
注意letters里面的元素可以是重复的，所以，不能在letters[mid]==target的时候直接返回mid+1。
注意二分查找的时候当letters[mid]>target的时候，有可能mid就是最终的答案，所以更新的时候，right=mid 而不是mid-1。
二分查找解法，时间复杂度O(log(n))，python代码：

class Solution(object):
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
def binary(letters,target):
left,right=0,len(letters)-1
while left<right:
mid=left+(right-left)/2
if letters[mid]<=target:
left=mid+1
else:
right=mid
return right if letters[right]>target else 0
idx=binary(letters,target)
return letters[idx]

直接比较法，时间复杂度O(n)，python代码：

class Solution(object):
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
for letter in letters:
if letter>target:
return letter
return letters[0]

明显是二分查找的速度更快。
二分查找c++代码：

class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int idx=binary(letters,target);
return letters[idx];
}
int binary(vector<char>&letters,char target)
{
int left=0,right=letters.size()-1;
while (left<right)
{
int mid=left+(right-left)/2;
if (letters[mid]<=target)
left=mid+1;
else
right=mid;
}
return letters[right]>target?right:0;
}
};

直接使用库函数：
python代码：

import bisect
class Solution:
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
idx=bisect.bisect_right(letters,target)
if idx==len(letters):
return letters[0]
else:
return letters[idx]

c++代码：

#include<algorithm>
using namespace std;
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
auto it =upper_bound(letters.begin(),letters.end(),target);
if (it==letters.end())
return letters[0];
else
return *it;
}
};

总结：
1.stl的<algorithm>中：
upper_bound(a+i,a+j,x)-a返回的是第一个大于x的数的坐标
upper_bound(a.begin(),a.end(),x)返回的是迭代器
low_bound(first,last,x)返回的是第一个大于等于x的数的指针或者迭代器
本题可以直接使用upper_bound()

2.python的bisect，先说明的是，使用这个模块的函数前先确保操作的列表是已排序的。
data=[2,4,7,9]

insort()函数，将某个数插入到data中，插入结果不会影响原有排序。

>>>bisect.insort(data,3)
>>>data
>>>[2,3,4,7,9]

bisect()函数，查找该数值将会插入的位置并返回，而不会插入。

>>>bisect.bisect(data,1)
0
>>>data
>>>[2,3,4,7,9]

接着看 bisect_left() 和 bisect_right() 函数，该函数用入处理将会插入重复数值的情况，返回将会插入的位置：

 #在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置
>>>bisect.bisect_left(data,4)
2
#在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置
>>>bisect.bisect_right(data,4)
3
>>>data
[2,3,4,7,9]

其对应的插入函数是insort_left () 和 insort_right() ：

>>>bisect.insort_left(data,4)
>>>data
[2,3,4,4,7,9]
>>>data=[2,3,4,7,9]
>>>bisect.insort_right(data,4)
>>>data
[2,3,4,4,7,9]

可见，单纯看其结果的话，两个函数的操作结果是一样的，其实插入的位置不同而已。

本题可以使用bisect.bisect_right(L,x)
上述两个库函数实际上都是用二分查找实现的。

最后

以上就是幽默柜子为你收集整理的744. Find Smallest Letter Greater Than Target（python+cpp）的全部内容，希望文章能够帮你解决744. Find Smallest Letter Greater Than Target（python+cpp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。