hash - 面试：如何有效地搜索字符串中第一次出现的字符？

Question

我的一位面试官问我如何有效地搜索字符串中第一次出现的字符。

我说使用散列，但他想要一种高效的内存处理方式。对字符串进行排序并执行二进制搜索是不可能的，因为索引会丢失。

面试官似乎对我的回答不太满意。还有什么我可以说的吗？

Answer 1

为什么不使用指针搜索第一次出现。这是最有效的查找方式（只需要 4 或 8 个字节的数据）。

unsigned long findIndex(char ch){
  char *str = "some really long; string; here";
  char *ptr = str;
  while(*ptr != ch || *ptr != '\0'){
     ptr++;
  }
  return (unsigned long)(ptr - str)
}

计算科学的基本定律：您可以优化空间或优化运行时间。

软件工程的基本法则：BEEP “计算机科学家”所说的，找到最佳的中间点。