jake1036

面试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 阅读(515) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理