Приступ заснован на реду за први знак који се не понавља у стриму  


Ниво тешкоће Средњи
Често питани у амазонка Флипкарт мицрософт ПаиУ иахоо
Хасх Повезана листа Ред низ

Изјава о проблему  

Проблем „Приступ заснован на реду за први знак који се не понавља у току“ наводи да сте добили ток који садржи мала слова карактера, пронађите први знак који се не понавља, кад год се новом току дода нови знак, а ако нема знака који се не понавља, вратите -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 и наставите да обрађујете следећи знак.
Види такође
Имплементација Декуе-а помоћу кружног низа

Анализа сложености за први непонављајући лик у току  

Будући да смо тачно прешли ток, сваки лик би могао бити гурнут у ред и уклоњен из реда тачно једном. Тако
Сложеност времена = Он)
Сложеност простора = Он)
где је н укупан број знакова у току.

код  

Јава код за први знак који се не понавља у току

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

Ц ++ код за први знак који се не понавља у току

#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