• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

    请实现一个函数用来找出字符流中第一个只出现一次的字符。

    举例说明

    例如,当从字符流中只读出前两个字符“Go”时,第一个只出现一次的字符是‘g’。当从该字符流中读出前六个字符“google”时,第一个只出现1次的字符是”l”。

    二、解题思路

    字符只能一个接着一个从字符流中读出来。可以定义一个数据容器来保存字符在字符流中的位置。当一个字符第一次从字符流中读出来时,把它在字符流中的位置保存到数据容器里。当这个字符再次从字符流中被读出来时,那么它就不是只出现一次的字符,也就可以被忽略了。这时把它在数据容器里保存的值更新成一个特殊的值(比如负值)。

    为了尽可能高校地解决这个问题,需要在O(1)时间内往容器里插入一个字符,以及更新一个字符对应的值。这个容器可以用哈希表来实现。用字符的ASCII码作为哈希表的键值,而把字符对应的位置作为哈希表的值。

    三、解题代码

    1. public class Test {
    2. /**
    3. * 题目:请实现一个函数用来找出字符流中第一个只出现一次的字符。
    4. */
    5. private static class CharStatistics {
    6. // 出现一次的标识
    7. private int index = 0;
    8. private int[] occurrence = new int[256];
    9. public CharStatistics() {
    10. for (int i = 0; i < occurrence.length; i++) {
    11. occurrence[i] = -1;
    12. }
    13. }
    14. private void insert(char ch) {
    15. if (ch > 255) {
    16. throw new IllegalArgumentException( ch + "must be a ASCII char");
    17. }
    18. // 只出现一次
    19. if (occurrence[ch] == -1) {
    20. occurrence[ch] = index;
    21. } else {
    22. // 出现了两次
    23. occurrence[ch] = -2;
    24. }
    25. index++;
    26. }
    27. public char firstAppearingOnce(String data) {
    28. if (data == null) {
    29. throw new IllegalArgumentException(data);
    30. }
    31. for (int i = 0; i < data.length(); i++) {
    32. insert(data.charAt(i));
    33. }
    34. char ch = '\0';
    35. // 用于记录最小的索引,对应的就是第一个不重复的数字
    36. int minIndex = Integer.MAX_VALUE;
    37. for (int i = 0; i < occurrence.length; i++) {
    38. if (occurrence[i] >= 0 && occurrence[i] < minIndex) {
    39. ch = (char) i;
    40. minIndex = occurrence[i];
    41. }
    42. }
    43. return ch;
    44. }
    45. }
    46. }