Zenn
😟

LeetCode 744. Find Smallest Letter Greater Than Target

2021/12/26に公開
Kotlin
LeetCode
tech

Question

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

昇順ソートされた文字配列lettersと文字列targetが与えられたときに、文字列targetよりアルファベット順に後に出てくるもので、文字配列lettersの中ではアルファベット順に最初に出てくるものを求める問題

Code

class Solution {
    fun nextGreatestLetter(letters: CharArray, target: Char): Char {

        var left = 0
        var right = letters.lastIndex

        while (left <= right) {
            val middle = left +(right -left)/2
            if (letters[middle] > target) {
                right = middle -1
            } else {
                left = middle +1
            }
        }
        // return letters[left%letters.size]
	return if (left <= letters.lastIndex) letters[left] else letters[0]
    }
}

class Solution {
    fun nextGreatestLetter(letters: CharArray, target: Char): Char {

        for (char in 'a'..'z') {
            if (char == target) {
                for (idx in letters.indices) {

                    if (char < letters[idx]) return letters[idx]
                    if (idx == letters.lastIndex) return letters[0]
                }
            }
        }
        return Char.MAX_VALUE
    }
}

ソートされている配列からtargetを探索するときは基本的には2分探索で指数時間で探しに行く。
leftがインデックスの外に行ってしまったときは先頭に戻る(the letters wrap around)必要があるので、left > letter.lastIndexのときletters[0]を返すようにする。letters[left%letters.size]でもできるかちょっと思いつかなかった。
後者の方が理論上計算量が大きくなる想定だが、実際にはこちらのほうが早かった。
制約が2 <= letters.length <= 10^4だったから？

Profile

  • 1つ目

    • Runtime: 208 ms ($O(logn))
    • Memory Usage: 37.9 MB

  • 2つ目

    • Runtime: 204 ms ($O(n^2))
    • Memory Usage: 38.2 MB

Submission

GitHubで編集を提案

Discussion