面試100 13第一個只出現一次的字符

第一個只出現一次的字符

方法1 ：
           第一個只出現一次的字符。
           (1)考慮使用一個hash表，將各個字符映射到表中，然后表中存儲有該字符出現的次數，以及首次出現的下標。
           (2)映射完成之后，掃描hash數組查找出現次數為1的字符，并且其首次出現下標為最小。

    缺點：
          需要存儲首次出現的下標，造成存儲位置浪費。

#include <iostream>

#include <vector>

#include <iterator>

using namespace std ;

struct Value{

int times ;

int index ;

} ;

const int N = 26 ;

const int MAX = 66536 ;

int hashstr(char * s , Value * list )

{

int i = 0 ;

int index = MAX ;

if(s == 0)

return index;

while(*s != '\0')

{

list[*s-'a'].times++ ;

if(list[*s-'a'].index == -1) //若是首次出現下標，則統計

list[*s-'a'].index = i ;

i++;

s++;

}

for(i = 0 ;i < N ; i++)

{

if(list[i].times == 1)

{

if(index > list[i].index) //求最小的下標

index = list[i].index ;

}

return index ;

}

int main()

{

int i ;

char s[] = "wabacckdeffbzw" ;

Value list[N] ;

for(i = 0;i < N ;i++)

{

list[i].times = 0 ;

list[i].index = -1 ;

}

int index = hashstr(s , list) ;

if(index == MAX)

cout<<"error"<<endl ;

else

cout<<s[index]<<endl ;

system("pause") ;

return 0 ;

}

方法2 ：

    建立一個長度為256的hash數組，掃描到對應的字符，即更新hash表內存儲出現的次數。
需要兩次掃描字符串，第一次掃描統計字符串的出現次數，第二次掃描確定出現一次的字符及其位置，比方法1，比較省空間。

代碼如下：

#include <iostream>

using namespace std ;

const int N = 256 ;

void hashstr(char * s , int * a)

{

char * p = s ;

while(*p)

{

a[*p]++ ; //自增

p++ ;

}

while(*s) //掃描第二遍，當掃描都出現次數為1的字符，即停止

{

if(a[*s] == 1)

{

cout<<*s ;

break;

}

s++ ;

}

int main()

{

char s[] = "wabacckdeffbz" ;

int a[N] ;

memset(a , 0 , sizeof(a)) ;

hashstr(s , a) ;

system("pause") ;

return 0 ;

}

posted on 2011-05-17 10:25 kahn 閱讀(540) 評論(0) 編輯收藏引用所屬分類: 算法相關

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 9-24MTK一面二面微軟筆試總結 2011-09-07xx移動創業公司筆試題編程之美2.7 最大公約數 O(n)實現刪除兩個數組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

面試100 13第一個只出現一次的字符

第一個只出現一次的字符