javascript - 如何提高Javascript/破解代码算法的性能？

Question

所以这是下面的问题，以及我的答案。我知道由于双重嵌套的for循环，效率是O(n^2)，所以我想知道是否有办法提高我的算法/函数的大O。

//设计一个算法并编写代码来删除字符串中的重复字符，而不使用任何额外的缓冲区。注意:一两个附加变量就可以了。数组的额外副本不是。

function removeDuplicates(str) {
    let arrayString = str.split("");
    let alphabetArray = [["a", 0],["b",0],["c",0],["d",0],["e",0],["f",0],["g",0],["h",0],["i",0],["j",0],["k",0],["l",0],["m",0],["n",0],["o",0],["p",0],["q",0],["r",0],["s",0],["t",0],["u",0],["v",0],["w",0],["x",0],["y",0],["z",0]]

    for (let i=0; i<arrayString.length; i++) {
        findCharacter(arrayString[i].toLowerCase(), alphabetArray);
    }

    removeCharacter(arrayString, alphabetArray);
};


function findCharacter(character, array) {
    for (let i=0; i<array.length; i++) {
        if (array[i][0] === character) {
        array[i][1]++;
        }
    }
} 

function removeCharacter(arrString, arrAlphabet) {
    let finalString = "";
    for (let i=0; i<arrString.length; i++) {
        for (let j=0; j<arrAlphabet.length; j++) {
            if (arrAlphabet[j][1] < 2 && arrString[i].toLowerCase() == arrAlphabet[j][0]) {
            finalString += arrString[i]
            }
        }
      } 
    console.log("The string with removed duplicates is:", finalString)
}

removeDuplicates("Hippotamuus")

Answer 1

相同大小写的所有字母的 ASCII/Unicode 字符代码是连续的。这允许进行重要的优化:您可以从字符计数数组中的 ASCII/Unicode 字符代码找到字符的索引。具体来说，字符计数数组中字符 c 的索引将为 c.charCodeAt(0) - 'a'.charCodeAt(0)。这使您可以在 O(1) 时间内查找和修改数组中的字符计数，从而将算法运行时间缩短为 O(n)。