刪除O（n）中字符串中的空格

Question

如何刪除複雜度爲O（n）的字符串中的空格。 我的方法是使用兩個索引。一個人會穿過繩子的長度。只有遇到非空字符時，其他纔會增加。 但我不確定這種方法。

TIA， 普利文

Answer 1

這種方法很好。 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...] 

需要注意的是，如果沒有在嚴格的空間克，它只是複製每一個字符。你可能會認爲你可以通過檢查是否優化它，而不是複製，但你可能會發現這個檢查和拷貝一樣貴。而且，除非您經常複製數兆字節的字符串，否則性能不會成爲問題。

也請記住，這將是未定義的行爲與const字符串，但這將是在任何就地修改的情況下。

Answer 2

你的方法聽起來不錯，並滿足使用要求。