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...] 

주, 즉 전혀 존재하지 않는 경우 strin에있는 공간 g, 모든 문자를 단순히 복사합니다. src == dst인지 아닌지 확인하여 최적화 할 수 있다고 생각할 수도 있지만, 그 수표가 사본만큼 비싸다는 것을 알게 될 것입니다. 또한 멀티 메가 바이트 문자열을 자주 복사하지 않는 한 성능이 문제가되지 않습니다.

또한 이것은 const 문자열로 정의되지 않은 동작이지만, 모든 내부 수정에서 그럴 수 있습니다.

Answer 2

귀하의 접근 방식은 미세한 사운드 및 요구 사항을 충족합니다.