面试题之在字符串中查找出第一个只出现一次的字符的位置 |
您所在的位置:网站首页 › 查找第一个字符为2的产品 › 面试题之在字符串中查找出第一个只出现一次的字符的位置 |
样例:比如“abcdabc”,第一个只出现一次的字符为d,位置为3
解决方案1:O(n*n)的复杂度 遍历字符串中的每个字符,然后用该字符在字符串中进行查找,如果没有找到和当前字符相同的字符。则当前字符为第一个 只出现一次的字符。
解决方案2:O(n)的复杂度 采取空间换时间的策略 开一个辅助数组,做哈希映射 第一次扫描时,更新在辅助数组中当前字符出现的次数。 hash查找的时间复杂度为o(1)。 第二次扫描时,在辅助数组中通过查辅助数组看当前字符是否只出现了一次,从头到尾的顺序遍历保证了“第一个”,辅助数组的查找保证了“只出现一次”。 code: #include using namespace std; int main() { string str="abcdabc"; //在字符串中查找出第一个只出现一次的字符 //o(n) 空间换时间 int a[300]; memset(a,0,sizeof(a)); //第一次遍历 统计各字符出现次数 for(int i=0;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |