algorithm - 面试题: Finding Next and Previous characters in a given string?

Question

我们有一种语言 X，它有一个字节和两个字节的字符。该语言具有以下特点。

1. 单字节字符值将始终小于或等于 127。
2. 在双字节字符中，第一个字节总是大于 127，第二个字节的值可以是任何值。

问题是，给定一个任意长度的字符串和指向字符串中某个字节的指针，我们必须找出前一个字符是什么，下一个字符是什么。

一种简单的方法是从字符串的开头开始，检查字节的值并比较指针，直到我们到达给定的指针。但在最坏的情况下，如果给定的指针指向给定字符串中的最后一个字节，我们必须遍历所有字符。

我想知道是否有更好的算法可以在恒定时间内给出结果，而不管字符串的长度如何？

Answer 1

不，恒定时间是不可能的，因为最坏的情况是，正如 Olexiy 所说，几乎整个字符串都是最高位设置的字节，您需要回溯到开头以找出第一个最高位- 在前两个字节序列中设置字节。

希望这种病态情况很少见，您可以一次退回一个字节，直到遇到任何低字节，在这种情况下，您可以确定之后的字节是一个人物。然后您可以再次向前走，直到遇到您原来的指针。