二分查找LeetCode 744 Find Smallest Letter Greater Than Target

LeetCode 744

Find Smallest Letter Greater Than Target

• Problem Description：
  返回比目标字母大且序号最小的字母。
  具体的题目信息：
  https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/
• Example:
  
• Solution:
  
  • 解题思路：题目给出的样例中存在重复字母，我们通过排序和插入得到一个从小到大排列且不重复的字母序列，然后通过二分查找确定是否能找到目标字母，如果可以找到，则返回该目标字母的下一位；如果找不到，则返回low指向的字母。
  • 编程实现：

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        sort(letters.begin(), letters.end());
        vector<char> arr;
        arr.push_back(letters[0]);
        char temp = letters[0];
        for (int i = 1; i < letters.size(); i++) {
            if(letters[i] != temp) {
                arr.push_back(letters[i]);
                temp = letters[i];
            }
        }
        int low = 0, high = arr.size()-1, mid, flag = 0, res;
        while(low<=high) {
            mid = low+(high-low)/2;
            if (arr[mid] == target) {
                flag = 1;
                break;
            } else if (arr[mid]>target) {
                high = mid-1;
            } else {
                low = mid+1;
            }
        }
        if (flag == 1)
            res = (mid+1)%arr.size();
        else
            res = low%arr.size();
        return arr[res];
    }
};