744. 寻找比目标字母大的最小字母

柔情只为你懂 2024-04-01 16:06 56阅读 0赞

### 744. 寻找比目标字母大的最小字母 ###

给你一个排序后的字符列表  l e t t e r s letters letters ，列表中只包含小写英文字母。另给出一个目标字母  t a r g e t target target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 t a r g e t = ′ z ′ target = 'z' target=′z′ 并且字符列表为  l e t t e r s = \[ ′ a ′ , ′ b ′ \] letters = \['a', 'b'\] letters=\[′a′,′b′\]，则答案返回  ′ a ′ 'a' ′a′

##### 示例 1： #####

> 输入: letters = \[“c”, “f”, “j”\]，target = “a”  
> 输出: “c”

##### 示例 2: #####

> 输入: letters = \[“c”,“f”,“j”\], target = “c”  
> 输出: “f”

##### 示例 3: #####

> 输入: letters = \[“c”,“f”,“j”\], target = “d”  
> 输出: “f”

##### 提示： #####

2 < = l e t t e r s . l e n g t h < = 1 0 4 2 <= letters.length <= 10^4 2<=letters.length<=104  
 l e t t e r s \[ i \] letters\[i\] letters\[i\] 是一个小写字母  
 l e t t e r s letters letters 按非递减顺序排序  
 l e t t e r s letters letters 最少包含两个不同的字母  
 t a r g e t target target 是一个小写字母

#### 思路：二分查找 ####

*  利用列表有序的特点，可以使用二分查找降低时间复杂度。
 *  首先比较目标字母和列表中的最后一个字母，当目标字母大于或等于列表中的最后一个字母时，答案是列表的首个字母。当目标字母小于列表中的最后一个字母时，列表中一定存在比目标字母大的字母，可以使用二分查找得到比目标字母大的最小字母。
 *  初始时，二分查找的范围是整个列表的下标范围。每次比较当前下标处的字母和目标字母，如果当前下标处的字母大于目标字母，则在当前下标以及当前下标的左侧继续查找，否则在当前下标的右侧继续查找。

#### 代码： ####

public class min_letter {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		char [] letters = {
        'c', 'f', 'j'};
    		char target = 'k';
    		System.out.println(nextGreatestLetter(letters, target));
    	}
    	public static char nextGreatestLetter(char[] letters, char target) {
        
    		int l = 0, h = letters.length - 1;
    		if(target >= letters[h])
    			return letters[0];
    		int t = (target - 'a' + 1) % 26;
    		while(l < h) {
        
    			int m = l + (h - l)/2;
    			if((letters[m] - 'a' + 1) <= t) {
        
    				l = m + 1;
    			}else{
        
    				h = m;
    			}
    		}
    		return letters[l];
        }
    }

##### 复杂度分析： #####

*  时间复杂度： O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)，其中  n n n 是列表  l e t t e r s letters letters 的长度。二分查找的时间复杂度是  O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)。
 *  空间复杂度： O ( 1 ) O(1) O(1)

##### 注：仅供学习参考 #####

来源：[力扣][Link 1]

[Link 1]: https://leetcode.cn/problems/find-smallest-letter-greater-than-target/description/