Удалить пробелы в строке в O (n) - PullRequest
Новая
       4

Удалить пробелы в строке в O (n)

2 голосов
/ 22 июня 2010

Как удалить пробелы в строке со сложностью O (n).Мой подход использует два индекса.Один будет проходить по длине на строку.Другое будет увеличиваться только тогда, когда встречается непустой символ.Но я не уверен в этом подходе.

TIA, Правин

Ответы [ 2 ]

7 голосов
/ 22 июня 2010

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

Псевдокод: 

def removeSpaces (str):
    src = pointer to str
    dst = src
    while not end-of-string marker at src:
        if character at src is not space:
            set character at dst to be character at src
            increment dst
        increment src
    place end-of-string marker at dst

- это в основном то, что вы пытаетесь сделать.

Поскольку он имеет один цикл, зависящий только от количества символов, он действительно равен O (n) сложность времени.

Следующая программа на C показывает это в действии: 

#include <stdio.h>

// Removes all spaces from a (non-const) string.

static void removeSpaces (char *str) {
    // Set up two pointers.

    char *src = str;
    char *dst = src;

    // Process all characters to end of string.

    while (*src != '\0') {
        // If it's not a space, transfer and increment destination.

        if (*src != ' ')
            *dst++ = *src;

        // Increment source no matter what.

        src++;
    }

    // Terminate the new string.

    *dst = '\0';
}


// Test program.

int main (void)
{
    char str[] = "This is a long    string with    lots of spaces...   ";
    printf ("Old string is [%s]\n", str);
    removeSpaces (str);
    printf ("New string is [%s]\n", str);
    return 0;
}

Запуск этого дает вам: 

Old string is [This is a long    string with    lots of spaces...   ]
New string is [Thisisalongstringwithlotsofspaces...]

Обратите внимание, что, если в строке нет пробелов, он просто копирует каждый символ поверх себя.Вы можете подумать, что вы можете оптимизировать его, проверив, если src == dst, а не копировать, но вы, вероятно, обнаружите, что проверка такая же дорогая, как и копия.И, если вы часто не копируете многомегабайтные строки, производительность здесь не будет проблемой.

Также имейте в виду, что это будет неопределенное поведение со строками const, но это будет иметь место в любом случае.модификация на месте.

3 голосов
/ 22 июня 2010

Ваш подход звучит нормально и соответствует требованию.

...