The topic of dry

You are given a sorted list of letters, containing only lowercase Letters. Given another target letter, look for the smallest letter in the sequence list that is larger than the target letter.

In comparison, the letters appear in a circular order. Here’s an example:

  • If the target letter is target = ‘z’ and the character list is letters = [‘a’, ‘b’], the answer returns ‘a’.

Example:

Input: letters = [" c ", "f" and "j"] output target = "a" : "c"Copy the code

Solution 1: Pointers

Code implementation:

Loop once, record the target value and the size in the array, and finally process the returned value according to the pointer value:

Execution time: 84 ms, beating 87.12% of all JavaScript commits

Memory consumption: 40 MB, beating 13.63% of all JavaScript commits

  var nextGreatestLetter = function (letters, target) {
    let length = letters.length;
    let index = 0;
    for (let i = 0; i < length; i++) {
      if (letters[i].charCodeAt() > target.charCodeAt()) {
        index++
      }
    }
    return index==length||index==0? letters[0]:letters[length-index]
  };
Copy the code

Solution 2: dichotomy

If the low pointer is normal (less than the length of the array), return the low element (since low is always greater than middle). If it is abnormal, return the first element of the array

Code implementation:

Execution time: 80 ms, beating 96.21% of all JavaScript commits

Memory consumption: 39.9 MB, beating 26.89% of all JavaScript commits

var nextGreatestLetter2 = function (letters, target) {
    let low = 0;
    let length = letters.length
    let high = letters.length - 1
    let middle = 0;
    while (low <= high) {
      middle = Math.floor((low + high) / 2);
      if (letters[middle].charCodeAt() > target.charCodeAt()) {
        high = middle - 1
      } else {
        low = middle + 1}}return low < length ? letters[low] : letters[0]};Copy the code