גישה מבוססת תור לדמות ראשונה שאינה חוזרת בזרם


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית Flipkart מיקרוסופט PayU יאהו
בליל רשימה מקושרת תור מחרוזת

הצהרת בעיה

הבעיה "גישה מבוססת תור לדמות ראשונה שאינה חוזרת בזרם" קובעת שאתה מקבל זרם המכיל אותיות קטנות תווים, מצא את התו הראשון שאינו חוזר בכל פעם שמתווסף לזרם דמות חדשה, ואם אין תו שאינו חוזר, חזור -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