在字符串中查找非重复字符的空间复杂度

Question

这里是一个简单的算法练习。问题是返回第一个非重复字符。例如，我有以下字符串：'abbbcdd'，答案为'a'，因为'a'出现在'c'之前。如果找不到重复的字符，它将返回'_'。

我的解决方案正常工作，但是我的问题是关于性能。问题语句说：“写一个只迭代字符串一次并使用O（1）附加内存的解决方案。”

这是我的代码：

console.log(solution('abbbcdd'))

function solution(str) {
  let chars = buildCharMap(str)
  for (let i in chars) {
    if (chars[i] === 1) {
      return i
    }
  }
  return '_'
}

function buildCharMap(str) {
  const charMap = {}
  for (let i = 0; i < str.length; i++) {
    !charMap[str[i]] ? charMap[str[i]] = 1 : charMap[str[i]]++
  }
  return charMap
}

我的答案满足空间复杂性的要求吗？

Answer 1

n的字符串上循环，而在另一个对象上严格使用

n键进行另一个循环。循环内的操作花费O（1）时间，并且循环是连续的（非嵌套），因此运行时间为O（n）。

空间复杂性稍微微妙一些。例如，如果输入是数字列表而不是字符串，那么我们可以直截了当地说charMap在最坏的情况下占用O（n）空间，因为列表中的所有数字可能都是不同。但是，对于字符串上的问题，我们必须意识到，可以由这些字符串组成的字符的字母有限。如果该字母的大小为[[a，则您的charMap对象最多可以具有

a键，因此空间复杂度为O（min（a，n）） 。

该字母通常在问题中是明确的-例如，如果保证输入中仅包含小写字母或仅包含字母和数字。否则，这可能是隐含的，因为字符串是由Unicode字符（或在较旧的语言中为ASCII字符）形成的。在前一种情况下，a = 26或62。在后一种情况下，a = 65,536或1,112,064，这取决于我们是在计算

code unit

还是code points，因为Javascript字符串被编码为UTF-16。无论哪种方式，如果a是一个常数，则O（a）空间是O（1）空间-尽管它可能是一个很大的常数。这意味着在实践中，您的算法确实使用O（1）空间。从理论上讲，如果问题陈述指定了固定的字母，则使用O（1）空间；否则使用O（min（a，

n

））空间；否则，它将使用O（1）空间。不是O（n）空间。假设是前者，那么您的解决方案确实满足问题的空间复杂性要求。[这引起了一个问题，为什么在分析数字列表上的算法时，我们同样不会说Javascript数字具有由IEEE 754 specification定义的浮点数字的有限“字母”。答案有点哲理。我们使用抽象的计算模型来分析运行时间和辅助空间，这些抽象模型通常假定数字，列表和其他数据结构的大小没有固定的限制。但是即使在这些模型中，我们也假定字符串是由某个字母组成的，如果问题中字母没有固定，则我们将字母大小设为变量a，我们认为该变量独立于n] >。这是一种分析字符串算法的明智方法，因为字母大小和字符串长度与我们通常感兴趣的问题无关。