数据结构|查找一个字符串中第一个只出现两/一次的字符数据结构|剑指offer

题目：查找一个字符串中第一个只出现两/一次的字符
一、查找一个字符串中第一个只出现两次的字符。
比如：“abcdefabcdefabc”中第一个只出现两次为‘d’，要求时间复杂度为O(N)，空间复杂度为O(1)。
分析问题：
方法1、O（N^2）
看到这道题时，最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较，如果后面出现两次该字符，那么该字符为第一个只出现两次的字符(注：内存循环需要全部遍历完字符)。如果字符串有n个字符，每个字符可能与后面的O(n)个字符相比较，因此这种思路时间复杂度是O(N^2)。
看代码：O（N^2）

char* FindFirstTwo(char *str) { int i = 0, j = 0; int len = strlen(str); int count = 0; //记录出现几次 for (; i < len; ++i) { char tmp = str[i]; count = 1; for (j = i + 1; j < len; ++j) { if (tmp == str[j]) count++; } if (count == 2) return str + i; } return NULL; } void TestFindFirstTwo() { char str[] = "abcdefabcdefabc"; char *res = FindFirstTwo(str); if (res) cout << *res << endl; }

【数据结构|查找一个字符串中第一个只出现两/一次的字符】方法2、
可以考虑到用空间来换取时间，遍历一遍字符串时，可以记录下字符次数。第二次遍历，比较哈希表里面的出现的次数

bool FindFirstTwo2(char *str) { int len = strlen(str); int hashtables[256] = { 0 }; //第一次遍历 for (int i = 0; i < len; ++i) { hashtables[str[i]]++; }//第二次遍历 for (int i = 0; i < len; ++i) { if (hashtables[str[i]] == 2) { cout << str[i] << endl; return true; } } return false; } void TestFindFirstTwo2() { char str[] = "abcdefabcdefabc"; bool flag = FindFirstTwo2(str); }

二、在一个字符串中找出第一个不重复的字符

char FindFirstOnlyChar(const char *s) { int num[26]={0}; int index[26]={0}; int i,len; len = strlen(s); for(i=0; iindex[i]) { pos = index[i]; } } if(len == pos) return -1; else return s[pos]; } }