用于流中第一个非重复字符的基于队列的方法  


难度级别 中等
经常问 亚马逊 Flipkart 微软 PayU 雅虎
哈希 链表 队列

问题陈述  

问题“针对流中第一个非重复字符的基于队列的方法”指出给您一个包含小写字母的流 字符,只要将新字符添加到流中,并且不存在非重复字符,则查找第一个非重复字符,并返回-1。

例子  

aabcddbe
a -1 b b b b c c

说明:如我们所见,除了第二个索引外,输出在所有位置都具有第一个非重复字符。 但是直到索引2,所有字符都已重复。 因此,-1打印在索引2上。

abcdabcd
a a a a b c d -1

 

用于流中第一个非重复字符的基于队列的方法Pin

流中第一个非重复字符的算法  

可以使用 队列。 因此,我们只需要维护一个字符队列,然后 排列 频率。 该数组存储流中每个字符的频率。
因此,对于流中的每个字符。 然后增加该字符的频率并将其推入队列。 检查队列开始处的字符,如果该字符的频率为1,则返回该字符。 否则,弹出字符,然后检查下一个字符。 如果队列变空,则返回-1并继续处理流中的其他字符。

  1. 创建一个字符队列和一个存储每个字符频率的数组。
  2. 一对一地处理流的输入。
  3. 对于流中当前输入的字符,请增加频率并将其推入队列。
  4. 检查队列前面的字符,如果该字符的频率为1,则打印该字符,否则删除队列中的第一个字符并重复步骤4。
  5. 如果在第4步中队列变空,则打印-1并继续处理下一个字符。
参见
使用圆形数组实现双端队列

流中第一个非重复字符的复杂度分析  

由于我们只对流进行了一次遍历,因此每个字符都可能被推入队列,并恰好从队列中删除一次。 所以
时间复杂度 = O(N)
空间复杂度 = O(N)
其中n是流中的字符总数。

代码  

流中第一个非重复字符的Java代码

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

class QueueBasedApproachForFirstNonRepeatingCharacterInAStream {
    private static void firstNonRepeatingCharacter(String stream) {
        // create a array to store frequency of characters
        int freq[] = new int[26];
        // create a queue
        Queue<Character> queue = new LinkedList<>();

        // traverse the stream character by character
        for (int i = 0; i < stream.length(); i++) {
            // current character of stream
            char curr = stream.charAt(i);
            // increase the frequency
            freq[curr - 'a']++;
            // push it to queue
            queue.add(curr);

            while (!queue.isEmpty()) {
                // check the frequency of first character in queue
                char front = queue.peek();
                if (freq[front - 'a'] == 1) {
                    // if freq is 1, print the first character
                    System.out.print(front + " ");
                    break;
                } else {
                    // else remove the first character
                    queue.poll();
                }
            }

            // if queue becomes empty, print -1
            if (queue.isEmpty()) {
                System.out.print("-1 ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        String stream1 = "aabcddbe";
        firstNonRepeatingCharacter(stream1);

        // Example 2
        String stream2 = "abcdabcd";
        firstNonRepeatingCharacter(stream2);
    }
}
a -1 b b b b c c 
a a a a b c d -1

流中第一个非重复字符的C ++代码

#include<bits/stdc++.h> 
using namespace std; 

void firstNonRepeatingCharacter(string stream) {
    // create a array to store frequency of characters
    int freq[26];
    for (int i = 0; i < 26; i++) {
        freq[i] = 0;
    }
    // create a queue
    queue<char> q;
    
    // traverse the stream character by character
    for (int i = 0; i < stream.length(); i++) {
        // current character of stream
        char c = stream[i];
        // increase the frequency
        freq[c - 'a']++;
        // push it to queue
        q.push(c);
        
        while (!q.empty()) {
            // check the frequency of first character in queue
            char front = q.front();
            if (freq[front - 'a'] == 1) {
                // if freq is 1, print the first character
                cout<<front<<" ";
                break;
            } else {
                // else remove the first character
                q.pop();
            }
        }
        
        // if queue becomes empty, print -1
        if (q.size() == 0) {
            cout<<"-1 ";
        }
    }
    cout<<endl;
}

int main() {
    // Example 1
    string stream1 = "aabcddbe";
    firstNonRepeatingCharacter(stream1);

    // Example 2
    string stream2 = "abcdabcd";
    firstNonRepeatingCharacter(stream2);
    
    return 0;
}
a -1 b b b b c c 
a a a a b c d -1