jake1036

My Links

Blog Stats

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

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

面試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) ;