Как это O (1) пространство, а не O (n) пространство.firstNotRepeatingCharacter Решение проблем - PullRequest
Новая
       6

Как это O (1) пространство, а не O (n) пространство.firstNotRepeatingCharacter Решение проблем

0 голосов
/ 30 января 2019

У меня проблемы с пониманием того, как следующее решение - это пространство O (1), а не пространство O (n).Задача кодирования заключается в следующем:

Напишите решение, которое перебирает строку только один раз и использует O (1) дополнительной памяти, поскольку это то, что вас попросят сделать во время реального интервью.

По заданной строке s найти и вернуть первый экземпляр неповторяющегося символа в ней.Если такого символа нет, верните '_'.

Ниже приведено решение с пробелом O (1). 

function firstNotRepeatingCharacters(s: string) : string {
    const chars: string[] = s.split('');
    let duplicates = {};
    let answer = '_';
    let indexAnswer = Number.MAX_SAFE_INTEGER;

    chars.forEach((element, index) => {
        if(!duplicates.hasOwnProperty(element)) {
            duplicates[element] = {
                count: 1,
                index
            }
        } else {
            duplicates[element].count++;
            duplicates[element].index = index;
        }
    });

    for(const key in duplicates) {
        if(duplicates[key].count === 1 && duplicates[key].index < indexAnswer) {
            answer = key;
            indexAnswer = duplicates[key].index;
        }
    }
    return answer;
}

console.log(firstNotRepeatingCharacter('abacabad'));
console.log(firstNotRepeatingCharacter('abacabaabacaba'));

Я не понимаю, как вышеприведенное решение является O (1) пробелом.Поскольку мы выполняем итерацию по нашему массиву, мы сопоставляем каждый элемент с объектом (дубликат).Я бы подумал, что это будет считаться O (n), может кто-нибудь прояснить, как это O (1) для меня.Спасибо.

Ответы [ 3 ]

0 голосов
/ 30 января 2019

Алгоритм имеет O (мин (a, n)) сложность пространства (где a - количество букв, используемых для охлаждения текста, например, для UTF8 a> 1M ).В худшем случае: строка с уникальными символами (в данном случае n <= a </strong>), например, abcdefgh объект duplicates имеет то же количество клавиш, что и цифровые буквы входной строки, - и то, что ясно дляВ этом случае размер используемой памяти зависит от n .

O (1) только для случая, когда строка содержит одну повторяющуюся букву, например aaaaaaa.

Бонус : Ваш код может быть"сжаты" таким образом:) 

function firstNotRepeatingCharacters(s, d={}, r="_") {  
  for(let i=0; i<s.length; i++) d[s[i]]=++d[s[i]]|0;  
  for(let i=s.length-1; i>=0; i--) if(!d[s[i]]) r=s[i];  
  return r;
}

console.log(firstNotRepeatingCharacters('abacabad'));
console.log(firstNotRepeatingCharacters('abacabaabacaba'));
0 голосов
/ 30 января 2019

Действительно, это 0 (1) сложность, но только из-за ограничений пространства.Так как у нас есть верхний предел.Это ограничение может быть UTF-16, это может быть количество английских букв.

Это ограничение, данное разработчиком.Сказав это, это только 0 (1) в ограничениях пространства, если код выше работает с конечным набором комбинаций.

Строка, ограниченная реализацией 64-битным символьным "массивом".Таким образом, емкость магазина, как правило, типа "String", составляет 2147483647 (231 - 1) символов.Это не совсем то, что 0 (1) представляет.Так что фактически это 0 (N) в ограничениях пространства.

Теперь ситуация здесь совершенно иная для ограничений сложности времени.В оптимальном сценарии должно быть 0 (N) + 0 (N - E) + 0 (N).

Объяснение: 1. Первый 0 (N), первый цикл проходит через все элементы 2.Второй 0 (N) об удалении.Код удаляет элементы из массива.3. 0 (N - E), второй forEach зацикливает последний извлеченный массив, поэтому у нас есть константа E.

И это предполагает, что структура данных является массивом.

Существует многоКопать здесь.

TL; DR

Это не 0 (1).

0 голосов
/ 30 января 2019

Использование памяти пропорционально количеству различных символов в строке.Число различных символов имеет верхний предел 52 (или какое-либо другое конечное значение), и потенциальное использование памяти не увеличивается, поскольку n увеличивается после того, как каждый из отдельных символов был замечен.

Таким образом, существует верхний предел использования памяти, который является постоянным (не зависит от n ), поэтому использование памяти равно O (1).

...