题目

给定一个 只包含小写字母的有序数组 letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子，如果目标字母 target = z 并且有序数组为 letters = ['a', 'b']，则答案返回 a。

示例:

  1. 输入:
  2. letters = ["c", "f", "j"]
  3. target = "a"
  4. 输出: "c"
  6. 输入:
  7. letters = ["c", "f", "j"]
  8. target = "c"
  9. 输出: "f"
  11. 输入:
  12. letters = ["c", "f", "j"]
  13. target = "d"
  14. 输出: "f"
  16. 输入:
  17. letters = ["c", "f", "j"]
  18. target = "g"
  19. 输出: "j"
  21. 输入:
  22. letters = ["c", "f", "j"]
  23. target = "j"
  24. 输出: "c"
  26. 输入:
  27. letters = ["c", "f", "j"]
  28. target = "k"
  29. 输出: "c"

注:

  • letters 长度范围在 [2, 10000] 区间内。
  • letters 仅由小写字母组成，最少包含两个不同的字母。
  • 目标字母 target 是一个小写字母。

方案一（二分查找，模板三）

func nextGreatestLetter(letters []byte, target byte) byte {
    // 特殊情况处理
    if target < letters[0] || target >= letters[len(letters)-1] {
        return letters[0]
    }

    // 二分查找
    var left, right = 0, len(letters) - 1
    for left + 1 < right {
        var mid = (left + right) / 2
        // if letters[mid] == target {
        //        return letters[mid+1]
        // } else 
        if letters[mid] > target && letters[mid - 1] < target {
            return letters[mid]
        } else if letters[mid] > target {
            right = mid
        } else {
            left = mid
        }
    }

    // 尾处理: 结束条件 left + 1 == right
    var index int
    if letters[right] > target {
        index = right
    }
    if letters[left] > target {
        index = left
    }

    return letters[index]
}
  • 注意上述代码中注释掉的部分，这样的判断是错误的, eg. ["e", "e", "e", "e", "e", "e", "n", "n", "n", "n"]

原文

https://leetcode-cn.com/explore/learn/card/binary-search/213/conclusion/852/