刪除字符串中的連續空格(只保留一個),O(n)時間複雜度,O(1)空間複雜度

出處:http://www.xuebuyuan.com/732322.html

昨天(2012/10/23)晚上,南大,科大訊飛宣講加筆試,題目很基礎,也很簡單,可是。。。沒認真弄。掛了,回來痛定思痛,今天南郵打算再去跑一趟。
       另一個哥們由於沒有使用內層循環(潛意識告訴他,那樣會增加複雜度,其實不會),使用了四個分支判斷,而我當時考慮的實現的需要,用了最笨的方法,涉及大量的元素移動(太爛了,居然當時出來還沾沾自喜,真是丟人)。
       這裡參考了《算法導論》中快速排序的劃分函數的寫法,設置兩個指針,一個用於遍歷,一個用於結果的拷貝。另外也參考了網上百度知道的一些朋友的類似事例程序
//trim a string by make  more than one blank to one blank
char* trim(char* a)
{
 int i=-1,j=0;
 for (;a[j]!='';j++)
 {
  if (a[j]==a[j+1] && a[j+1]==' ')
  {
   //skip more than one blank
   while (a[j]==' ')
   {
    ++j;
   }
   --j;// go back to the last blank
  }
  a[++i]=a[j];
 }
 a[++i]='';
 return a;
}
int main( void ) 
{
 
 char a[100]="a b  c  d  e                  f";
 print(a);
 print(trim(a));
 return 0;
}
未經允許不得轉載:GoMCU » 刪除字符串中的連續空格(只保留一個),O(n)時間複雜度,O(1)空間複雜度