LeetCode 744. Find Smallest Letter Greater Than Target

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCodeの744. Find Smallest Letter Greater Than Targetを解いてみました。

設問

与えられた昇順に整列済みの文字列の中で、targetより大きい文字の中で一番小さい文字を返す問題。

解

文字charは数字としても扱うことができるので、整列済みの数列の探索としてとらえることができます。

整列済みの配列なので、2分探索が使えます。

計算量はO(logN)で、メモリ消費量はO(1)です。

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

ちなみに愚直に全探索する方法。 計算量はO(N)で、メモリ消費量はO(1)です。

class Solution {
   public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        for (auto c : letters) {
            if (c > target) {
                return c;
            }
        }
        return letters[0];
    }
};