面试题之在字符串中查找出第一个只出现一次的字符的位置

您所在的位置:网站首页 查找第一个字符为2的产品 面试题之在字符串中查找出第一个只出现一次的字符的位置

面试题之在字符串中查找出第一个只出现一次的字符的位置

2024-06-17 01:08| 来源: 网络整理| 查看: 265

样例:比如“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