# LeetCode Easy 744. Find Smallest Letter Greater Than Target

tags: leetcode

問題

• Explore
• Problems

アイデア

文字の入った整列済みの配列の中からtargetよりも大きい中で最小の文字を見つけるという問題です．

数字の形が変わっただけでただ比較すれば良いだけです．

解法

zより大きいのはaであるように大きさは循環するということを考慮します．

探索する範囲の左端と右端を決めます．そして，その中央がtargetよりも小さいときは左端を中央+1にします．

それ以外では右端を中央にします．

もしzの場合は最終的に左端が右端となります．これを処理するために最後に左端を入力配列の大きさで割った数を添え字とした数を出力する．

計算量

配列の長さを$N$とします

• 時間計算量
  • $O(\log N)$
• 空間計算量
  • $O(1)$

C++

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