題目一：字符串中第一個(gè)只出現(xiàn)一次的字符笋籽。
在一個(gè)字符串(0<=字符串長度<=10000哈恰，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符啊楚，并返回它的位置帮碰，如果沒有則返回 -1（需要區(qū)分大小寫）代兵。
練習(xí)地址
https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c
https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
參考答案
class Solution {
public char firstUniqChar(String s) {
if (s == null) {
return ' ';
}
int[] hashTable = new int[256];
for (char c : s.toCharArray()) {
hashTable[c]++;
}
for (char c : s.toCharArray()) {
if (hashTable[c] == 1) {
return c;
}
}
return ' ';
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)尼酿。
- 空間復(fù)雜度：O(1)。
題目二：字符流中第一個(gè)只出現(xiàn)一次的字符植影。
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)裳擎，用來找出字符流中第一個(gè)只出現(xiàn)一次的字符。例如思币，當(dāng)從字符流中只讀出前兩個(gè)字符"go"時(shí)鹿响，第一個(gè)只出現(xiàn)一次的字符是'g'。當(dāng)從該字符流中讀出前六個(gè)字符“google"時(shí)谷饿，第一個(gè)只出現(xiàn)一次的字符是'l'惶我。
練習(xí)地址
https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720
參考答案
public class Solution {
// positions[i]: A character with ASCII value i;
// positions[i] = -1: The character has not found;
// positions[i] = -2: The character has been found for multiple times;
// positions[i] >= 0: The character has been found only once.
private int[] positions = new int[256];
private int position;
public Solution() {
for (int i = 0; i < 256; i++) {
positions[i] = -1;
}
}
// Insert one char from stringstream
public void Insert(char ch) {
if (positions[ch] == -1) {
positions[ch] = position;
} else if (positions[ch] > -1) {
positions[ch] = -2;
}
position++;
}
// return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
char ch = '#';
int min = Integer.MAX_VALUE;
for (int i = 0; i < 256; i++) {
if (positions[i] > -1 && positions[i] < min) {
ch = (char) i;
min = positions[ch];
}
}
return ch;
}
}
時(shí)間復(fù)雜度
- 插入時(shí)間復(fù)雜度：O(1)。
- 插入空間復(fù)雜度：O(1)博投。
- 尋找時(shí)間復(fù)雜度：O(1)绸贡。
- 尋找空間復(fù)雜度：O(1)。
實(shí)際尋找的時(shí)間和空間復(fù)雜度為256，當(dāng)少量數(shù)據(jù)時(shí)采用題目一的方法更有效听怕，當(dāng)大量數(shù)據(jù)時(shí)本題解法才更好捧挺。
