😀前言
在编程面试和实际项目中，处理字符流并找到其中第一个不重复的字符是一个常见的挑战。本文将详细介绍如何利用 Java 来实现这一功能，并提供一个有效的解决方案。

😀字符流中第一个不重复的字符

牛客网

😊问题描述

我们需要设计一个函数来处理字符流，目标是找到流中第一个只出现一次的字符。例如：

• 当字符流中读到 “go” 时，第一个不重复的字符是 “g”。
• 当读到 “google” 时，第一个不重复的字符变成了 “l”。

我们的任务是实现两个函数：

• Insert(char ch)：用于将字符插入到字符流中。
• FirstAppearingOnce()：返回字符流中第一个只出现一次的字符。如果没有，返回 #。

string caseout = “”;

1.读入测试用例字符串casein

2.如果对应语言有Init()函数的话，执行Init() 函数

3.循环遍历字符串里的每一个字符ch {

Insert(ch);

caseout += FirstAppearingOnce()

}

\2. 输出caseout，进行比较。

🤔示例1

输入：“google”

返回值：“ggg#ll”

🤔示例2

输入：“abcdee”

返回值：“aaaaaa”

🥰解题思路

解决这个问题的一种有效方法是结合使用统计数组和队列来跟踪字符的出现次数和顺序。

1. 统计字符出现次数：
   由于字符都是 ASCII 码范围内的字符，我们可以使用一个大小为 128 的整型数组来记录每个字符出现的次数。通过将字符的 ASCII 码作为索引，可以快速地更新和查询每个字符的出现次数。
2. 维护字符顺序：
   使用队列来保存字符流中的字符顺序。每次插入新字符时，我们将其添加到队列中。同时，我们通过检查队列头部的字符来找出第一个出现一次的字符。如果队列头部的字符不再是只出现一次，我们就将其从队列中移除。
3. 返回第一个不重复字符：
   FirstAppearingOnce() 函数负责返回队列头部的字符。如果队列为空，则说明没有不重复的字符，返回 #。

😁代码实现

import java.util.LinkedList;
import java.util.Queue;

public class FirstUniqueCharInStream {

    // 数组用于记录每个字符的出现次数
    private int[] cnts = new int[128];
    // 队列用于维护字符的顺序
    private Queue<Character> queue = new LinkedList<>();

    // 将字符插入到字符流中
    public void Insert(char ch) {
        cnts[ch]++;
        queue.add(ch);
        // 移除队列头部的非唯一字符
        while (!queue.isEmpty() && cnts[queue.peek()] > 1) {
            queue.poll();
        }
    }

    // 返回字符流中第一个只出现一次的字符
    public char FirstAppearingOnce() {
        return queue.isEmpty() ? '#' : queue.peek();
    }

    public static void main(String[] args) {
        FirstUniqueCharInStream stream = new FirstUniqueCharInStream();
        String testString = "google";
        StringBuilder result = new StringBuilder();
        for (char ch : testString.toCharArray()) {
            stream.Insert(ch);
            result.append(stream.FirstAppearingOnce());
        }
        System.out.println(result.toString()); // 输出 "ggg#ll"
    }
}

💝代码详解

1. cnts 数组：用于记录每个字符的出现次数。因为 ASCII 码范围是 0-127，所以我们使用一个大小为 128 的数组。
2. queue 队列：用于保存字符的顺序，确保我们能快速找到第一个不重复的字符。
3. Insert 函数：每次插入新字符时，更新 cnts 数组，并将字符添加到队列中。如果队列头部的字符不再唯一，则从队列中移除。
4. FirstAppearingOnce 函数：返回队列头部的字符，或在队列为空时返回 #。

💝复杂度分析

• 时间复杂度：每次插入和查找操作的时间复杂度均为 O(1)，因此整体时间复杂度为 O(n)。
• 空间复杂度：我们使用了一个大小为 128 的数组和一个队列，空间复杂度为 O(n)。

😄总结

通过使用统计数组和队列的组合，我们能够高效地处理字符流并找到第一个不重复的字符。这种方法在字符流处理中表现优异，适用于需要实时处理数据流的场景。如果你在编码面试中遇到类似问题，不妨试试这个解决方案。