刪除字符串中的連續空格（只保留一個），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;
}

相關推薦