jake1036

My Links

Blog Stats

Posts - 101
Stories - 0
Comments - 23
Trackbacks - 0

常用鏈接

留言簿(1)

隨筆分類(lèi)

隨筆檔案

搜索

閱讀排行榜

評(píng)論排行榜

面試100 13第一個(gè)只出現(xiàn)一次的字符

第一個(gè)只出現(xiàn)一次的字符

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

    缺點(diǎn)：
          需要存儲(chǔ)首次出現(xiàn)的下標(biāo)，造成存儲(chǔ)位置浪費(fèi)。

#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) //若是首次出現(xiàn)下標(biāo)，則統(tǒng)計(jì)

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

i++;

s++;

}

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

{

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

{

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

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 ：

    建立一個(gè)長(zhǎng)度為256的hash數(shù)組，掃描到對(duì)應(yīng)的字符，即更新hash表內(nèi)存儲(chǔ)出現(xiàn)的次數(shù)。
需要兩次掃描字符串，第一次掃描統(tǒng)計(jì)字符串的出現(xiàn)次數(shù)，第二次掃描確定出現(xiàn)一次的字符及其位置，比方法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) //掃描第二遍，當(dāng)掃描都出現(xiàn)次數(shù)為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) ;