樣例：比如“abcdabc”，第一個只出現(xiàn)一次的字符為d，位置為3

?

解決方案1：O（n*n)的復(fù)雜度

遍歷字符串中的每個字符，然后用該字符在字符串中進(jìn)行查找，如果沒有找到和當(dāng)前字符相同的字符。則當(dāng)前字符為第一個 只出現(xiàn)一次的字符。

?

?

解決方案2：O(n)的復(fù)雜度

采取空間換時間的策略

開一個輔助數(shù)組，做哈希映射

第一次掃描時，更新在輔助數(shù)組中當(dāng)前字符出現(xiàn)的次數(shù)。

hash查找的時間復(fù)雜度為o(1)。

第二次掃描時，在輔助數(shù)組中通過查輔助數(shù)組看當(dāng)前字符是否只出現(xiàn)了一次，從頭到尾的順序遍歷保證了“第一個”，輔助數(shù)組的查找保證了“只出現(xiàn)一次”。

code：

#include <bits/stdc++.h> using namespace std;int main() {string str="abcdabc";//在字符串中查找出第一個只出現(xiàn)一次的字符//o(n) 空間換時間int a[300];memset(a,0,sizeof(a));//第一次遍歷 統(tǒng)計各字符出現(xiàn)次數(shù)for(int i=0;i<str.length();i++){a[str[i]]++;}//第二次遍歷 輔助數(shù)組做哈希映射int pos=-1;for(int i=0;i<str.length();i++){if(a[str[i]]==1){pos=i;break;}}cout<<pos<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/yinbiao/p/10469880.html

總結(jié)

以上是生活随笔為你收集整理的面试题之在字符串中查找出第一个只出现一次的字符的位置的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。