时间复杂度哈希表

Question

我以两种方式实现了一个简单的算法。一种使用 indexOf，另一种使用哈希表。

问题：给定一个任意的赎金票据字符串和另一个包含所有杂志字母的字符串，编写一个函数，如果赎金票据可以从杂志中构造出来，该函数将返回 true；否则，它将返回 false。

第一。时间复杂度为 O(N^2) 是因为我在 ransomNote 中有 N 个字母并且我可以在 indexOf 中进行 N 次搜索吗？

var canConstruct = function(ransomNote, magazine) {

    if(magazine.length < ransomNote.length) return false;

    

    const arr = magazine.split("");

    for(let i=0; i<ransomNote.length; i++) {

        if(arr.indexOf(ransomNote[i]) < 0)

            return false;

        const index = arr.indexOf(ransomNote[i]);

        arr.splice(index, 1);

    }

    

    return true;

};

第二个。时间复杂度是多少？哈希表是否使其成为 O(N)？

var canConstruct = function(ransomNote, magazine) {

    if(magazine.length < ransomNote.length) return false;

    

    const map = new Map();

    for(let i =0; i<magazine.length; i++) {

        if(map.has(magazine[i]))

            map.set(magazine[i], map.get(magazine[i])+1);

        else

            map.set(magazine[i], 1);

    }

    

    for(let i=0; i<ransomNote.length; i++) {

        if(!map.has(ransomNote[i]))

            return false;

        else {

            const x = map.get(ransomNote[i]) - 1;

            if(x > 0)

                map.set(ransomNote[i], x)

            else

                map.delete(ransomNote[i]);

        }

    }

    

    return true;

};

Answer 1

第一个解决方案好吧，你必须考虑一件事，尤其是在第一个解决方案中，split, slice &nbsp;and indexOf方法都有自己的时间复杂度。假设你在杂志上有 m 封信。当你将它拆分成数组时，你已经在那里使用了 O(m) 时间复杂度（当然还有 O(m) 空间复杂度，因为你将它全部存储在一个大小为 m 的新数组中）。现在您输入一个将运行 n 次的 for 循环（其中 n 是 ransomNote 中的字母数）。所以就在那时和那里你有 O(m * n) 时间复杂度。indexOf 操作也将被调用 n 次，但需要注意的是每次调用时它都会运行 O(m)。您可以在那里看到您开始增加时间复杂度的速度有多快。我认为它类似于 O(3 * m * n^2) ，它四舍五入到O(m * n^n)时间复杂度。我强烈建议不要indexOf多次调用，只需调用一次并将其结果存储在某处。你要么有一个索引，要么-1意味着找不到它。第二种解决方案好多了。在这里你填充了一个哈希映射（所以使用了一些额外的内存，但考虑到你也首先使用了一个拆分并存储它，它应该大致相同）。然后你只需简单地循环遍历 randomNote 并在 hashMap 中找到一个字母。在地图中查找一个字母的时间复杂度为 O(1)，因此它对于此类算法非常有用。我认为最终复杂度为O(n * m)比第一个要好得多。希望我对你有意义。如果您愿意，我们可以在您回复后的评论中更深入地进行空间分析