剑指offer-54、字符流中第一个不重复的字符
<h2 id="题描述">题⽬描述</h2><p>请实现⼀个函数⽤来找出字符流中第⼀个只出现⼀次的字符。例如，当从字符流中只读出前两个字符" go "时，第⼀个只出现⼀次的字符是" g "。当从该字符流中读出前六个字符“ google "时，第⼀个只出现⼀次的字符是" l "。</p>
<p>返回值描述：如果当前字符流没有存在出现⼀次的字符，返回 # 字符。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="有序哈希表">有序哈希表</h3>
<p>可以直接使用哈希的数据结构来存取我们的字符，对与重复的字符可以对值进行统计或者标记都行。这里要用LinkedHashMap，因为题目要求到了要出现的第一个不重复的字符，所以如果不使用有序map的话，那么我们就不能保证取到的是第一个不重复的字符。</p>
<pre><code class="language-java">public class Solution {
//Insert one char from stringstream
//因为后面要遍历保证有序，所以这里使用LinkedHashMap
Map<Character,Integer> map = new LinkedHashMap<>();
public void Insert(char ch){
if(map.containsKey(ch)){
map.put(ch,-1);
}else{
map.put(ch,1);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
for(Character i : map.keySet()){
if(map.get(i) == 1){
return i;
}
}
return '#';
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：插入O(1)，查询最坏O(n)</li>
<li><strong>空间复杂度</strong>：O(n)</li>
</ul>
<h3 id="队列计数数组最优">队列+计数数组(最优)</h3>
<p>结合了队列的先进先出特性和数组的快速访问能力，能够高效解决动态字符流中的首个不重复字符查找问题</p>
<pre><code class="language-java">public class Solution {
private int[] count = new int;// ASCII字符计数数组
private Queue<Character> queue = new LinkedList<>();// 维护候选字符顺序
// 插入字符到流中
public void Insert(char ch) {
count++;// 字符出现次数加1
queue.add(ch);// 字符加入队列
// 清理队列头部已重复的字符
while (!queue.isEmpty() && count > 1) {
queue.poll();
}
}
// 返回当前第一个不重复字符
public char FirstAppearingOnce() {
return queue.isEmpty() ? '#' : queue.peek();
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：每个字符的插入操作是均摊O(1)，查询操作是严格的O(1)</li>
<li><strong>空间复杂度</strong>：O(1)（固定大小的数组和队列）</li>
</ul>
<h3 id="双数组记录">双数组记录</h3>
<p>通过记录字符首次出现的位置和状态，在查询时进行全局扫描</p>
<pre><code class="language-java">public class Solution {
private int[] position = new int;// 记录字符位置或状态
private int index = 1;// 当前字符位置索引
public Solution() {
// 初始化，-1表示未出现过
for (int i = 0; i < 128; i++) {
position = -1;
}
}
public void Insert(char ch) {
if (position == -1) {
// 第一次出现，记录位置
position = index;
} else if (position > 0) {
// 重复出现，标记为-2
position = -2;
}
index++;
}
public char FirstAppearingOnce() {
int minIndex = Integer.MAX_VALUE;
char result = '#';
// 扫描找到最小正整数值对应的字符
for (int i = 0; i < 128; i++) {
if (position > 0 && position < minIndex) {
minIndex = position;
result = (char) i;
}
}
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：插入O(1)，查询O(1)（固定128次循环）</li>
<li><strong>空间复杂度</strong>：O(1)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19377767
頁:
[1]