题目一:字符串中第一个只出现一次的字符。
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写)。
练习地址
https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c
参考答案
public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) {
return -1;
}
int[] counts = new int[256];
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
counts[c]++;
}
for (int i = 0; i < str.length(); i++) {
if (counts[str.charAt(i)] == 1) {
return i;
}
}
return -1;
}
}
复杂度分析
- 时间复杂度: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,当少量数据时采用题目一的方法更有效,当大量数据时本题解法才更好。
网友评论