스트림에서 첫 번째 비 반복 문자에 대한 대기열 기반 접근 방식


난이도 중급
자주 묻는 질문 아마존 Flipkart Microsoft 알레그로 Yahoo
해시 연결된 목록

문제 정책

"스트림에서 첫 번째 비 반복 문자에 대한 큐 기반 접근 방식"문제는 소문자를 포함하는 스트림이 제공된다는 것을 나타냅니다. 문자, 새 문자가 스트림에 추가 될 때마다 반복되지 않는 첫 번째 문자를 찾고, 반복되지 않는 문자가 없으면 -1을 반환합니다.

aabcddbe
a -1 b b b b c c

설명: 우리가 볼 수 있듯이 출력에는 두 번째 인덱스를 제외한 모든 곳에서 첫 번째 반복되지 않는 문자가 있습니다. 그러나 색인 2까지 모든 문자가 반복되었습니다. 따라서 인덱스 1에 -2이 인쇄됩니다.

abcdabcd
a a a a b c d -1

 

스트림에서 첫 번째 비 반복 문자에 대한 대기열 기반 접근 방식

스트림의 첫 번째 반복되지 않는 문자에 대한 알고리즘

위의 문제는 열. 따라서 우리는 캐릭터의 대기열을 유지하고 정렬 주파수의. 배열은 스트림에있는 모든 문자의 빈도를 저장합니다.
따라서 스트림의 모든 문자에 대해. 그런 다음 해당 캐릭터의 빈도를 높이고 대기열로 푸시합니다. 대기열 시작 부분의 문자를 확인하고 해당 문자의 빈도가 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