Question

744. Find Smallest Letter Greater Than Target

中文文档

Description

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return _the smallest character in _letters_ that is lexicographically greater than _target. If such a character does not exist, return the first character in letters.

 

Example 1:

Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.

Example 2:

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.

Example 3:

Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

 

Constraints:

• 2 <= letters.length <= 104
• letters[i] is a lowercase English letter.
• letters is sorted in non-decreasing order.
• letters contains at least two different characters.
• target is a lowercase English letter.

Solutions

Solution 1

class Solution:
  def nextGreatestLetter(self, letters: List[str], target: str) -> str:
    left, right = 0, len(letters)
    while left < right:
      mid = (left + right) >> 1
      if ord(letters[mid]) > ord(target):
        right = mid
      else:
        left = mid + 1
    return letters[left % len(letters)]

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

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

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

function nextGreatestLetter(letters: string[], target: string): string {
  const n = letters.length;
  let left = 0;
  let right = letters.length;
  while (left < right) {
    let mid = (left + right) >>> 1;
    if (letters[mid] > target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return letters[left % n];
}

impl Solution {
  pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
    *letters
      .iter()
      .find(|&&c| c > target)
      .unwrap_or(&letters[0])
  }
}

class Solution {
  /**
   * @param String[] $letters
   * @param String $target
   * @return String
   */
  function nextGreatestLetter($letters, $target) {
    $left = 0;
    $right = count($letters);
    while ($left <= $right) {
      $mid = floor($left + ($right - $left) / 2);
      if ($letters[$mid] > $target) {
        $right = $mid - 1;
      } else {
        $left = $mid + 1;
      }
    }
    if ($left >= count($letters)) {
      return $letters[0];
    } else {
      return $letters[$left];
    }
  }
}

Solution 2

impl Solution {
  pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
    let n = letters.len();
    let mut left = 0;
    let mut right = n;
    while left < right {
      let mid = left + (right - left) / 2;
      if letters[mid] > target {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    letters[left % n]
  }
}