Рубрики

Найти первый неповторяющийся символ из потока символов

По заданному потоку символов найдите первый неповторяющийся символ из потока. Вы должны указать первый неповторяющийся символ за O (1) в любой момент.

Если мы следуем первому подходу, обсуждаемому здесь , то нам нужно сохранить поток, чтобы мы могли пересечь его еще раз, чтобы найти первый неповторяющийся символ в любой момент. Если мы используем расширенный подход, описанный в том же посте , нам нужно проходить через массив count каждый раз, когда запрашивается первый неповторяющийся элемент. Мы можем найти первый неповторяющийся символ из потока в любой момент, не пересекая массив.

Идея заключается в том , чтобы использовать DLL (D oubly L L чернила IST) , чтобы эффективно получить первый неповторяющийся символ из потока. DLL содержит все неповторяющиеся символы по порядку, т. Е. Глава DLL содержит первый неповторяющийся символ, второй узел содержит второй неповторяющийся и т. Д.
Мы также поддерживаем два массива: один массив предназначен для хранения символов, которые уже посещались два или более раз, мы называем его повторным [], другой массив представляет собой массив указателей на узлы связанного списка, мы называем его inDLL []. Размер обоих массивов равен размеру алфавита, который обычно составляет 256.

  1. Создайте пустую DLL. Также создайте два массива inDLL [] и повторный [] размером 256. inDLL — это массив указателей на узлы DLL. repeat [] — логический массив, repeat [x] — true, если x повторяется два или более раз, в противном случае — false. inDLL [x] содержит указатель на узел DLL, если в DLL присутствует символ x, в противном случае NULL.
  2. Инициализируйте все записи inDLL [] как NULL и повторите [] как false.
  3. Чтобы получить первый неповторяющийся символ, верните символ в начало DLL.
  4. Ниже приведены шаги для обработки нового символа 'x' в потоке.
    • Если значение [x] равно true, игнорируйте этот символ (x уже повторяется два или более раз в потоке)
    • Если повтор [x] равен false, а inDLL [x] равен NULL (x виден впервые). Добавьте x к DLL и сохраните адрес нового узла DLL в inDLL [x].
    • Если повтор [x] равен false и inDLL [x] не равен NULL (x виден во второй раз). Получите DLL-узел x, используя inDLL [x], и удалите узел. Кроме того, отметьте inDLL [x] как NULL и повторите [x] как true.

Обратите внимание, что добавление нового узла в DLL является операцией O (1), если мы поддерживаем хвостовой указатель. Удаление узла из DLL также является O (1) . Таким образом, обе операции, добавление нового символа и поиск первого неповторяющегося символа занимают O (1) времени.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C / C ++

// Программа на C ++ для поиска первой
// неповторяющийся символ
// из потока символов
#include <iostream>
#define MAX_CHAR 256

using namespace std;

  
// Узел связанного списка

struct node {

    char a;

    struct node *next, *prev;

};

  
// Вспомогательная функция для добавления символа x в конце
// DLL. Обратите внимание, что функция может изменить голову и хвост
// указатели, поэтому указатели на эти указатели передаются.

void appendNode(struct node** head_ref, struct node** tail_ref,

                char x)

{

    struct node* temp = new node;

    temp->a = x;

    temp->prev = temp->next = NULL;

  

    if (*head_ref == NULL) {

        *head_ref = *tail_ref = temp;

        return;

    }

    (*tail_ref)->next = temp;

    temp->prev = *tail_ref;

    *tail_ref = temp;

}

  
// Утилита для удаления узла 'temp' из библиотеки DLL.
// Обратите внимание, что функция может изменять указатели головы и хвоста,
// поэтому указатели на эти указатели передаются.

void removeNode(struct node** head_ref, struct node** tail_ref,

                struct node* temp)

{

    if (*head_ref == NULL)

        return;

  

    if (*head_ref == temp)

        *head_ref = (*head_ref)->next;

    if (*tail_ref == temp)

        *tail_ref = (*tail_ref)->prev;

    if (temp->next != NULL)

        temp->next->prev = temp->prev;

    if (temp->prev != NULL)

        temp->prev->next = temp->next;

  

    delete (temp);

}

  

void findFirstNonRepeating()

{

    // inDLL [x] содержит указатель на

    // узел DLL, если x присутствует

    // в DLL. Если x отсутствует, то inDLL [x] равен NULL

    struct node* inDLL[MAX_CHAR];

  

    // repeat [x] равно true, если x повторяется два или более раз.

    // Если x не виден до сих пор или x виден только один раз. тогда

    // Повторно [x] ложно

    bool repeated[MAX_CHAR];

  

    // Инициализируем два вышеупомянутых массива

    struct node *head = NULL, *tail = NULL;

    for (int i = 0; i < MAX_CHAR; i++) {

        inDLL[i] = NULL;

        repeated[i] = false;

    }

  

    // Давайте рассмотрим следующий поток и увидим процесс

    char stream[] = "geeksforgeeksandgeeksquizfor";

    for (int i = 0; stream[i]; i++) {

        char x = stream[i];

        cout << "Reading " << x << " from stream n";

  

        // Мы обрабатываем этот символ, только если он не произошел

        // или произошло только один раз. повторный [х] истина, если х

        // повторяется дважды или более

        if (!repeated[x]) {

            // Если символ отсутствует в DLL, добавьте его в

            // конец DLL.

            if (inDLL[x] == NULL) {

                appendNode(&head, &tail, stream[i]);

                inDLL[x] = tail;

            }

            else // В противном случае удалите этот символ из DLL

            {

                removeNode(&head, &tail, inDLL[x]);

                inDLL[x] = NULL;

                repeated[x] = true; // Также помечаем как повторный

            }

        }

  

        // Вывести текущий первый неповторяющийся символ из

        // ручей

        if (head != NULL)

            cout << "First non-repeating character so far is "

                 << head->a << endl;

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    findFirstNonRepeating();

    return 0;

}

Джава

// Java-программа для поиска первого неповторяющегося символа
// из потока символов

  

import java.util.ArrayList;

import java.util.List;

  

public class NonReapeatingC {

    final static int MAX_CHAR = 256;

  

    static void findFirstNonRepeating()

    {

        // inDLL [x] содержит указатель на узел DLL, если x присутствует

        // в DLL. Если x отсутствует, то inDLL [x] равен NULL

        List<Character> inDLL = new ArrayList<Character>();

  

        // repeat [x] равно true, если x повторяется два или более раз.

        // Если x не виден до сих пор или x виден только один раз. тогда

        // Повторно [x] ложно

        boolean[] repeated = new boolean[MAX_CHAR];

  

        // Давайте рассмотрим следующий поток и увидим процесс

        String stream = "geeksforgeeksandgeeksquizfor";

        for (int i = 0; i < stream.length(); i++) {

            char x = stream.charAt(i);

            System.out.println("Reading " + x + " from stream n");

  

            // Мы обрабатываем этот символ, только если он не произошел

            // или произошло только один раз. повторный [х] истина, если х

            // повторяется дважды или более

            if (!repeated[x]) {

                // Если символ отсутствует в DLL, добавьте его в

                // конец DLL.

                if (!(inDLL.contains(x))) {

                    inDLL.add(x);

                }

                else // В противном случае удалите этот символ из DLL

                {

                    inDLL.remove((Character)x);

                    repeated[x] = true; // Также помечаем как повторный

                }

            }

  

            // Вывести текущий первый неповторяющийся символ из

            // ручей

            if (inDLL.size() != 0) {

                System.out.print("First non-repeating character so far is ");

                System.out.println(inDLL.get(0));

            }

        }

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args)

    {

        findFirstNonRepeating();

    }

}
// Этот код предоставлен Sumit Ghosh

питон

# Программа Python, чтобы найти первый неповторяющийся символ из
# поток символов

MAX_CHAR = 256

  

def findFirstNonRepeating():

  

    # inDLL [x] содержит указатель на узел DLL, если x присутствует

    # в DLL. Если x отсутствует, то inDLL [x] равен NULL

    inDLL = [] * MAX_CHAR

  

    # repeat [x] равно true, если x повторяется два или более раз.

    # Если x не виден до сих пор или x виден только один раз. тогда

    # повторяется [x] ложно

    repeated = [False] * MAX_CHAR

  

    # Давайте рассмотрим следующий поток и посмотрим процесс

    stream = "geeksforgeeksandgeeksquizfor"

    for i in xrange(len(stream)):

        x = stream[i]

        print "Reading " + x + " from stream"

  

        # Мы обрабатываем этот символ, только если он не произошел

        # или произошло только один раз. повторный [х] истина, если х

        # повторяется дважды или более

        if not repeated[ord(x)]:

  

            # Если персонажа нет в DLL, добавьте это

            # в конце DLL

            if not x in inDLL:

                inDLL.append(x)

            else:

                inDLL.remove(x)

  

        if len(inDLL) != 0:

            print "First non-repeating character so far is ",

            print str(inDLL[0])

  
# Драйверная программа
findFirstNonRepeating()

  
# Этот код предоставлен BHAVYA JAIN

C #

// AC # программа для поиска первого неповторяющегося символа
// из потока символов

using System;

using System.Collections.Generic;

  

public class NonReapeatingC {

    readonly static int MAX_CHAR = 256;

  

    static void findFirstNonRepeating()

    {

        // inDLL [x] содержит указатель на узел DLL, если x присутствует

        // в DLL. Если x отсутствует, то inDLL [x] равен NULL

        List<char> inDLL = new List<char>();

  

        // repeat [x] равно true, если x повторяется два или более раз.

        // Если x не виден до сих пор или x виден только один раз. тогда

        // Повторно [x] ложно

        bool[] repeated = new bool[MAX_CHAR];

  

        // Давайте рассмотрим следующий поток и увидим процесс

        String stream = "geeksforgeeksandgeeksquizfor";

        for (int i = 0; i < stream.Length; i++) {

            char x = stream[i];

            Console.WriteLine("Reading " + x + " from stream n");

  

            // Мы обрабатываем этот символ, только если он не произошел

            // или произошло только один раз. повторный [х] истина, если х

            // повторяется дважды или более

            if (!repeated[x]) {

                // Если символ отсутствует в DLL, добавьте его в

                // конец DLL.

                if (!(inDLL.Contains(x))) {

                    inDLL.Add(x);

                }

                else // В противном случае удалите этот символ из DLL

                {

                    inDLL.Remove((char)x);

                    repeated[x] = true; // Также помечаем как повторный

                }

            }

  

            // Вывести текущий первый неповторяющийся символ из

            // ручей

            if (inDLL.Count != 0) {

                Console.Write("First non-repeating character so far is ");

                Console.WriteLine(inDLL[0]);

            }

        }

    }

  

    / * Код водителя * /

    public static void Main(String[] args)

    {

        findFirstNonRepeating();

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Reading g from stream
First non-repeating character so far is g
Reading e from stream
First non-repeating character so far is g
Reading e from stream
First non-repeating character so far is g
Reading k from stream
First non-repeating character so far is g
Reading s from stream
First non-repeating character so far is g
Reading f from stream
First non-repeating character so far is g
Reading o from stream
First non-repeating character so far is g
Reading r from stream
First non-repeating character so far is g
Reading g from stream
First non-repeating character so far is k
Reading e from stream
First non-repeating character so far is k
Reading e from stream
First non-repeating character so far is k
Reading k from stream
First non-repeating character so far is s
Reading s from stream
First non-repeating character so far is f
Reading a from stream
First non-repeating character so far is f
Reading n from stream
First non-repeating character so far is f
Reading d from stream
First non-repeating character so far is f
Reading g from stream
First non-repeating character so far is f
Reading e from stream
First non-repeating character so far is f
Reading e from stream
First non-repeating character so far is f
Reading k from stream
First non-repeating character so far is f
Reading s from stream
First non-repeating character so far is f
Reading q from stream
First non-repeating character so far is f
Reading u from stream
First non-repeating character so far is f
Reading i from stream
First non-repeating character so far is f
Reading z from stream
First non-repeating character so far is f
Reading f from stream
First non-repeating character so far is o
Reading o from stream
First non-repeating character so far is r
Reading r from stream
First non-repeating character so far is a

Эта статья предоставлена Амитом Джейном . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти первый неповторяющийся символ из потока символов

0.00 (0%) 0 votes