题目一：字符串中第一个只出现一次的字符。
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符，并返回它的位置，如果没有则返回 -1（需要区分大小写）。
练习地址
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 ' ';
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
题目二：字符流中第一个只出现一次的字符。
请实现一个函数，用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是'g'。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是'l'。
练习地址
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;
}
}
时间复杂度
- 插入时间复杂度：O(1)。
- 插入空间复杂度：O(1)。
- 寻找时间复杂度：O(1)。
- 寻找空间复杂度：O(1)。
实际寻找的时间和空间复杂度为256，当少量数据时采用题目一的方法更有效，当大量数据时本题解法才更好。
