744. Find Smallest Letter Greater Than Target

leetcode easy

#array#csharp#easy#graph#leetcode#search#sort#string#two-pointers

Task

Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах.

Пример:

Input: letters = ["c","f","j"], target = "a"

Output: "c"

C# solution

matched/original

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

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public char NextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return letters[left % letters.size()];
    }
}

Java solution

matched/original

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

JavaScript solution

matched/original

var nextGreatestLetter = function(letters, target) {
    let left = 0;
    let right = letters.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (letters[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return letters[left % letters.length];
};

Python solution

matched/original

def nextGreatestLetter(letters, target):
    left, right = 0, len(letters) - 1
    while left <= right:
        mid = (left + right) // 2
        if letters[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return letters[left % len(letters)]

Go solution

matched/original

package main

func nextGreatestLetter(letters []byte, target byte) byte {
    left, right := 0, len(letters)-1
    for left <= right {
        mid := (left + right) / 2
        if letters[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return letters[left % len(letters)]
}

Explanation

Algorithm

Использовать бинарный поиск для нахождения позиции первого символа в letters, который лексикографически больше target.

Если найденный символ существует, вернуть его.

Если такого символа не существует, вернуть первый символ в letters.

😎