首页 > 代码库 > IT公司100题-17-第一个只出现一次的字符
IT公司100题-17-第一个只出现一次的字符
问题描述：
在一个字符串中找到第一个只出现一次的字符。例如输入asdertrtdsaf，输出e。
分析：
最简单的方法是直接遍历，时间复杂度为O(n^2)。
进一步思考：
字符串中的字符，只有256种可能性，使用字符的为下标，扫描一遍，存储各个字符在字符串中的出现。第二次扫描字符串，查看每个字符在字符串中的出现次数，如果为1，输出即可。
代码实现：
// 17.cc#include#include#includeusing namespace std;char find_char(const char* str) { if (!str) return ‘\0‘; const size_t size = 256; size_t hash_table[size]; memset(hash_table, 0, sizeof(size_t) * size); // 第一遍遍历，统计每个字符出现次数 char* p = const_cast<char*>(str); while (*p) { hash_table[*p]++; p++; } // 第二遍遍历，查找出现次数为1的字符 p = const_cast<char*>(str); while(*p) { if (1 == hash_table[*p]) return *p; p++; } return ‘\0‘;}int main() { string s; cout << "please input a str:" << endl; cin >> s; char c = find_char(s.c_str()); if (c != ‘\0‘) cout << "The first char is: " << c << endl; else cout << "No char appears only once." << endl; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。