Google 2006年的一道笔试题,难度系数低
题目描写叙述:
在一个字符串中找到第一个仅仅出现一次的字符。如输入abaccdeff,则输出b。
逻辑分析:
1、简单粗暴O(n^2),一个显而易见的想法是像冒泡排序一样,採用两个循环,内层循环对外层判定元素arr[i]进行轮询,当发现arr[i] == arr[j]时,本次循环终止,显然,时间复杂度O(n^2),不使用额外空间。
#include <stdio.h> #include <stdlib.h> #include <string.h> void findSingle(char *arr, int len) { int i,j; for(i=0;i<len;i++) { for(j=i+1;j<len;j++) { if(arr[i] == arr[j]) { break; } if(j == len - 1) { printf("%c",arr[i]); return ; } } } } int main() { char str[] = "abaccdeff"; findSingle(str,strlen(str)); return 0; }
void findSingle(char *arr, int len) { int hashtable[26] = {0}; int i; for(i=0;i<len;i++) hashtable[arr[i]-'a']++; for(i=0;i<len;i++) { if(hashtable[arr[i]-'a'] == 1) { printf("%c\n",arr[i]); break; } } if(i >= len) { printf("无满足字符\n"); } }
3、扩展:一般来讲,对于字符串的问题,通常借助ASCII和哈希解决,上述代码2模拟小型哈希,仅仅对26个小写字母做了处理,扩展则使用2^8=256长度哈希。这里,不再小题大做。
在一个字符串中找到第一个仅仅出现一次的字符,布布扣,bubuko.com
原文:http://www.cnblogs.com/lcchuguo/p/3808353.html