Как улучшить производительность этого алгоритма Javascript / Cracking the code?

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

Я не был уверен, что имелось ввиду:

... без использования дополнительного буфера.

Так что я подумал, что мне нужно сделать это за один цикл, и позвольте мне сказать, если это не так.

Я работал на основе того, что предоставленная вами функция дает правильный вывод, вы просто искали, чтобы она работала быстрее. Функция ниже дает правильный вывод и работает намного быстрее с любой большой строкой с большим количеством дубликатов, которые я добавляю.

function removeDuplicates(originalString) {
    let outputString = '';
    let lastChar = '';
    let lastCharOccurences = 1;

    for (let char = 0; char < originalString.length; char++) {
        outputString += originalString[char];

        if (lastChar === originalString[char]) {
            lastCharOccurences++;
            continue;
        }
        
        if (lastCharOccurences > 1) {
            outputString = outputString.slice(0, outputString.length - (lastCharOccurences + 1)) + originalString[char];
            lastCharOccurences = 1;
        }

        lastChar = originalString[char];
    }

    console.log("The string with removed duplicates is:", outputString)
}

removeDuplicates("Hippotamuus")

Опять, извините, если я неправильно понял сообщение ...

Answer 2

Исходя из вашего описания, я предполагаю, что входные данные являются строкой (которая является неизменяемой в javascript), и я не уверен, что именно означает «одна или две дополнительные переменные» , означающие так, основываясь на ваша реализация, я собираюсь предположить, что это нормально использовать O (N) пробел. Я думаю, что для увеличения сложности времени реализации отличаются в зависимости от требований к выводимой строке.

Предположение1: порядок вывода строки в том порядке, в котором она появляется в первый раз. например. "bcabcc" -> "bca"

Предположим, длина s равна N, в следующей реализации используется пространство O (N) и время O (N).

 function removeDuplicates(s) {
    const set = new Set(); // use set so that insertion and lookup time is o(1)
    let res = "";
    for (let i = 0; i < s.length; i++) {
        if (!set.has(s[i])) {
            set.add(s[i]);
            res += s[i];
        }
    }
    return res;
  }

Предположение2: выводимая строка должна быть в порядке возрастания.

Вы можете использовать быструю сортировку , чтобы выполнить сортировку на месте, а затем перебрать отсортированный массив, чтобы добавить последний видимый элемент в результат. Обратите внимание, что вам может понадобиться сначала разбить строку на массив. Таким образом, реализация будет использовать O (N) пространство, а средняя сложность по времени будет O (NlogN) * ​​1014 *

Предположение3: результат является наименьшим в лексикографическом порядке среди всех возможных результатов. например. "bcabcc" -> "abc"

В следующей реализации используется пространство O (N) и время O (N).

const removeDuplicates = function(s) {
    const stack = []; // stack and set are in sync
    const set = new Set(); // use set to make lookup faster
    const lastPos = getLastPos(s);
    let curVal;
    let lastOnStack;

    for (let i = 0; i < s.length; i++) {
        curVal = s[i];
        if (!set.has(curVal)) {
            while(stack.length > 0 && stack[stack.length - 1] > curVal && lastPos[stack[stack.length - 1]] > i) {
                set.delete(stack[stack.length - 1]);
                stack.pop();
            }
            set.add(curVal);
            stack.push(curVal);
        }
    }
    return stack.join('');
};

const getLastPos = (s) => {
    // get the last index of each unique character
    const lastPosMap = {};
    for (let i = 0; i < s.length; i++) {
        lastPosMap[s[i]] = i;
    }
    return lastPosMap;
}

Answer 3

Есть небольшая хитрость "без использования дополнительного буфера", хотя я не вижу способа улучшить сложность O(n^2) без использования хэш-карты, чтобы определить, был ли виден определенный символ. Хитрость заключается в том, чтобы обойти буфер входной строки (предположим, что это массив JavaScript, поскольку строки в JavaScript являются неизменяемыми) и перезаписать текущий символ следующим уникальным символом, если текущий символ является дубликатом. Наконец, отметьте конец полученной строки нулевым символом.

псевдокод:

i = 1
pointer = 1

while string[i]:
  if not seen(string[i]):
    string[pointer] = string[i]
    pointer = pointer + 1
  i = i + 1

mark string end at pointer

Функция seen может занять O(n) время и O(1) пробел или O(1) время и O(|alphabet|) пробел, если мы используем хэш-карту.

Answer 4

Коды символов ASCII / Unicode всех букв одного и того же регистра являются последовательными. Это позволяет выполнить важную оптимизацию: вы можете найти индекс символа в массиве счетчиков символов из его кода символов ASCII / Unicode. В частности, индекс символа c в массиве символов будет c.charCodeAt(0) - 'a'.charCodeAt(0). Это позволяет вам искать и изменять количество символов в массиве за O(1) время, что снижает время выполнения алгоритма до O(n).