如何使用 JavaScript 查找字符串中的第一个不重复字符？

Question

我正在尝试解决数据结构和算法（DSA）中的一个常见问题：使用 JavaScript 查找字符串中的第一个非重复字符。该函数应该迭代字符串并返回第一个不重复的字符。如果不存在这样的字符，则应返回

null

。

例如：

findFirstNonRepeatingChar("swiss"); // Output: "w"
findFirstNonRepeatingChar("aabbcc"); // Output: null
 

我尝试通过使用嵌套的

for

循环遍历字符串两次，并对照其他字符检查每个字符来解决此问题。然而，这种方法对于长字符串来说似乎效率低下，因为它的时间复杂度是 O(n²)。

我期望找到一个更优化的解决方案，可能使用像哈希图这样的数据结构来将时间复杂度降低到 O(n)，但我无法想出实现。

这是我到目前为止所拥有的：

function findFirstNonRepeatingChar(str) {
    for (let i = 0; i < str.length; i++) {
        let isUnique = true;
        for (let j = 0; j < str.length; j++) {
            if (i !== j && str[i] === str[j]) {
                isUnique = false;
                break;
            }
        }
        if (isUnique) {
            return str[i];
        }
    }
    return null;
}

这适用于小输入，但对于大字符串来说会变得非常慢。我希望获得有关如何优化此解决方案的指导。

Answer 1

我会使用 Map 来计算每个字符出现的频率。 0次、1次、1次以上。

P.s.如果您的输入是 ASCII，您可以使用 array[int] 作为映射来完成。

第一遍：迭代您的输入并填充地图条目 第二遍：迭代并查找当前字符，直到找到具有“超过 1 次”地图条目的字符并将其作为结果返回。