开发者社区> 大数据> 正文

哈希表对字符串的高效处理

简介: 哈希表对字符串的高效处理方法。

哈希表对字符串的高效处理

哈希表(散列表)是一种非常高效的查找数据结构,在原理上也与其他的查找不尽相同,它回避了关键字之间反复比较的繁琐,而是直接一步到位查找结果。当然,这也带来了记录之间没有任何关联的弊端。应该说,散列表对于那些查找性能要求高,记录之间关系无要求的数据有非常好的适用性。注意对散列函数的选择和处理冲突的方法。

Hash表是使用 O(1)时间进行数据的插入、删除和查找,但是 hash 表不保证表中数据的有序性,这样在 hash 表中查找最大数据或者最小数据的时间是 O(N) 。

 

/* 字符串中完成过滤重复字符的功能,

【输入】:1.常字符串;2.字符串长度;3.【out】用于输出过滤后的字符串.

【输出】:过滤后的字符串。

*/

思路1

循环判定法。第1步,先记录字符串中第1个字符;第2步,然后从第2个字符开始,判定其和其前面的字符是否相同,不相同的话,则统计进去;相同的话则继续遍历,直到字符串末尾(遇到’0’)。时间复杂度:O(n2)。

思路2

哈希表过滤法。第1步,初始化一个哈希表,用以存储字符(key)及字符出现的次数;第2步,遍历哈希表,进行统计计数;第3步,输出统计次数为1及统计次数多余1的(输出1次)。时间复杂度:O(n)。

//循环判定法过滤掉重复字符

void stringFilter(const char*pInputStr, long lInputLen, char *pOutputStr)
{
       if(pInputStr== NULL || lInputLen == 0 || pOutputStr == NULL)
       {
              return;
       }
      
       intnCnt = 0;
       *pOutputStr= pInputStr[0];            //先处理第一个
       ++nCnt;
      
       intnNotEqualCnt = 0;                 //统计计数
       for(inti = 1; i < lInputLen; i++)
       {
              nNotEqualCnt= 0;
              for(intj = i-1; j >=0; j--)
              {
                     if(pInputStr[i]!= pInputStr[j])
                     {
                            ++nNotEqualCnt;
                     }
              }
             
              if(nNotEqualCnt== i)  //和前面的都不一样.
              {
                     pOutputStr[nCnt++]= pInputStr[i];
              }
             
       }//endfor
       pOutputStr[nCnt]= '\0';
}

//哈希表法过滤字符串中的重复字符

void stringFilterFast(const char*pInputStr, long lInputLen, char *pOutputStr)
{
       charrstChar = '\0';
       boolbNotRepeatFound = false;
       constunsigned int size = 256;
       unsignedint hashTable[size];
       constchar* pHashKey = pInputStr;
       intoutPutCnt = 0;
      
       if(pInputStr== NULL)
       {
              return;
       }
      
       //初始化哈希表
       for(unsignedint i = 0; i < size; i++)
       {
              hashTable[i]= 0;
       }
      
       //将pString读入到哈希表中
       while(*pHashKey!= '\0')
       {
              cout<< *pHashKey << "\t";
              hashTable[*pHashKey]++;    //统计计数
              pHashKey++;
       }    
 
       //读取哈希表,对只出现1次的进行存储,对出现多次的进行1次存储。
       pHashKey= pInputStr;
       while(*pHashKey!= '\0')
       {
              if((hashTable[*(pHashKey)])== 1)   //仅有一次,
              {
                     pOutputStr[outPutCnt++]= *pHashKey;
              }
              elseif((hashTable[*(pHashKey)]) > 1) // 多余一次,统计第一次
              {
                     pOutputStr[outPutCnt++]= *pHashKey;
                     hashTable[*(pHashKey)]= 0;
              }
              pHashKey++;
       }
       pOutputStr[outPutCnt]= '\0';
 
}
 
int main()
{
       constchar* strSrc = "desdefedeffdsswwwwwwwwwwdd";//"desdefedeffdssw";
       char*strRst =new char[strlen(strSrc)+1];
       stringFilter(strSrc,strlen(strSrc), strRst);
       cout<< strRst << endl;
       if (NULL != strRst){  delete[] strRst;  strRst = NULL;}      return 0;
}

 

//哈希表法查找字符串中第一个不重复的字符

【功能】:查找字符串中第一个不重复的字符。

【输入】:字符串。

【输出】:第一个不重复的字符。

时间复杂度O(n),思路类似于上面的哈希表过滤法。

char FirstNotRepeatingChar(constchar* pString)
{
       charrstChar = '\0';
       boolbNotRepeatFound = false;
       constunsigned int size = 256;
       unsignedchar hashTable[size];
       constchar* pHashKey = pString;
 
       if(pString== NULL)
       {
              returnrstChar;
       }
 
       //初始化哈希表
       for(unsignedint i = 0; i < size; i++)
       {
              hashTable[i] = 0;
       }
      
       //将pString存入到哈希表中
       while(*pHashKey!= '\0')
       {
              hashTable[*(pHashKey++)]++;    //统计计数
       }
 
       //读取哈希表,找到第一个=1的字符,bNotRepeatFound用于查找。.
       pHashKey= pString;
       while(*pHashKey!= '\0')
       {
              if((hashTable[*(pHashKey)]) == 1)
              {
                     bNotRepeatFound= true;
                     rstChar= *pHashKey;
                     break;
              }
              pHashKey++;
       }
 
       if(bNotRepeatFound)
       {
              cout<< "The first not Repeate char is " << rstChar <<endl;
       }
       else
       {
              cout<< "The first not Repeate char is not Exist " << endl;
       }
 
       returnrstChar;
}
 
int main()
{
       constchar* strSrc = "google";
       constchar* strSrc2 = "yyy@163.com";
       constchar* strSrc3 = "aabbccddeeff";
       constchar* strsrc4 = "11111111";  
                                                                                                                   
       constchar* strArray[4] = {strSrc, strSrc2, strSrc3, strsrc4};
 
      for(inti = 0; i < 4; i++)
      {
              FirstNotRepeatingChar(strArray[i]);
       }
 
       return0;
}

举一反三

百度面试题】对于一个海量的文件中存储着不同的URL,用最小的时间复杂度去除重复的URL。可借鉴字符串处理的哈希表过滤法。不过,这里的大文件等价于之前的字符串,这里的URL等价于之前的字符。

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章