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

题目

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

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

如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

解答

二分法

class Solution { public char nextGreatestLetter(char[] letters, char target) { // 二分法 int left = 0; int right = letters.length-1; //注意数组的上限遍历时从0-length-1 int ans = 0; while (left <= right){ int mid = (left + right)/2; if(letters[mid]>target){ ans = mid; right = mid -1; }else{ left = mid + 1; } } return letters[ans]; } } 可以省去ans变量，使用right/left来表示，但是返回前要判断一下特殊情况。 if(right == letters.length-1) right = -1; return letters[right+1];

540. 有序数组中的单一元素(M)

leetcode

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8] 输出: 2

示例 2:

输入: [3,3,7,7,10,11,11] 输出: 10

解决方案

暴力法

略

二分法

，根据mid值和左右哪个相等，去掉相等的之后如果是奇数就是含有目标的区域。mid和左右相等，左右侧奇偶数共组成四种确定边界的情况。 具体详解见官方

class Solution { public int singleNonDuplicate(int[] nums) { int left = 0; int right = nums.length-1; while(left < right){ int mid = (left + right )/2; boolean sideNumIsEven = (right - mid)%2 == 0; //每一侧偶数为truetrue //中间值和右侧相等 if(nums[mid] == nums[mid + 1]){ if(sideNumIsEven){ //右侧为偶数，去掉一个变成奇数个。存在目标值 left = mid+2; }else{ //右侧为奇数个，去掉一个变成偶数，目标不在右侧区域 //修改右侧 right = mid -1; } }else if(nums[mid] == nums[mid-1]){// 中间值和左侧相等 //左侧为偶数个，去掉一个相同的变成奇数个，存在目标值 if(sideNumIsEven){ // 目标在左侧区域，更新右侧上限 right = mid -2; }else{ //去掉一个相同的为偶数个，目标值在右侧 // 更新左侧边界 left = mid + 1; } }else{ //mid刚好就是目标值。 return nums[mid]; } } return nums[left] ; } }