int[] streamFlag = new int[128];
int count = 1;
public void Insert(char ch) {
if (streamFlag[ch] == 0) {
streamFlag[ch] = count;
count++;
} else if (streamFlag[ch] != -1) {
for (int i = 0; i < 128; i++) {
if (streamFlag[i] > streamFlag[ch]) { // 把在此字符后出现的字符顺序提前一位
streamFlag[i]--;
}
}
streamFlag[ch] = -1; // 重复出现直接置为-1
count--;
}
}
public char FirstAppearingOnce() {
for (int i = 0; i < 128; i++) {
if (streamFlag[i] == 1) {
return (char) i;
}
}
return '#';
} 总共就128个Ascii码,用streamFlag记录字符出现的先后顺序,插入时更新先后顺序,每次都找streaFlag为1的字符即可。
时间、空间复杂度O(1)



京公网安备 11010502036488号