Дамжуулалт дахь эхний давтагдаагүй тэмдэгтэд дараалалд суурилсан хандлага


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Flipkart Microsoft- PayU Yahoo
Хаш Холбогдсон жагсаалт дараалал String

Асуудлын мэдэгдэл

"Урсгал дахь эхний давтагдаагүй тэмдэгтэд дараалалд суурилсан хандлага" гэсэн асуудал нь танд жижиг үсгийг багтаасан урсгал өгөхийг зааж өгнө тэмдэгтүүд, урсгалд шинэ тэмдэгт нэмэгдэх бүрт эхний давтагдаагүй тэмдэгтийг олох ба хэрэв давтагдахгүй тэмдэгт байхгүй бол -1.

жишээ нь

aabcddbe
a -1 b b b b c c

Тайлбар: Эндээс харахад гаралт нь хоёр дахь индексээс бусад хаана ч давтагдаагүй эхний шинж чанартай байдаг. Гэхдээ 2-р индекс хүртэл бүх тэмдэгтүүд давтагдав. Тэгэхээр -1 индекс 2 дээр хэвлэгдэнэ.

abcdabcd
a a a a b c d -1

 

Дамжуулалт дахь эхний давтагдаагүй тэмдэгтэд дараалалд суурилсан хандлага

Урсгал дахь эхний давтагдахгүй тэмдэгтийн алгоритм

Дээрх асуудлыг a дараалал. Тиймээс бид зөвхөн тэмдэгтүүдийн дарааллыг хадгалах хэрэгтэй массив давтамж. Массив нь урсгал дахь тэмдэгт бүрийн давтамжийг хадгалдаг.
Ийнхүү урсгал дахь дүр болгоны хувьд. Дараа нь тухайн тэмдэгтийн давтамжийг нэмэгдүүлж, дараалалд оруулаарай. Дарааллын эхэнд тэмдэгтийг шалгана уу, хэрэв тухайн тэмдэгтийн давтамж 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