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)