删除o(n)中字符串中的空格

这种方法很好。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 但在任何就地修改中都是如此。

你的方法听起来不错,符合要求。