Рубрики

Возврат максимального встречающегося символа во входной строке

Напишите эффективную функцию для возврата максимального числа встречающихся символов во входной строке, например, если входной строкой является «test», то функция должна возвращать «t».


Алгоритм:

Одним из очевидных подходов к решению этой проблемы было бы отсортировать входную строку и затем пройти через отсортированную строку, чтобы найти символ, встречающийся максимальное количество раз. Давайте посмотрим, сможем ли мы улучшить это. Поэтому мы будем использовать технику под названием «Хеширование». При этом, когда мы пересекаем строку, мы хешируем каждый символ в массив символов ASCII.

Input string = “test”
1: Construct character count array from the input string.
  count['e'] = 1
  count['s'] = 1
  count['t'] = 2

2: Return the index of maximum value in count array (returns ‘t’).

Как правило, ASCII-символы равны 256, поэтому мы используем размер массива Hash как 256. Но если мы знаем, что наша входная строка будет содержать символы со значением только от 0 до 127, мы можем ограничить размер массива Hash как 128. Аналогично, на основе дополнительных При известной информации о входной строке размер массива Hash может быть ограничен 26.

Реализация:

C ++

// C ++ программа для вывода максимального встречающегося символа
// в строке
#include<bits/stdc++.h>
#define ASCII_SIZE 256

using namespace std;

  

char getMaxOccuringChar(char* str)

{

    // Создать массив для подсчета отдельных

    // символы и инициализируем массив как 0

    int count[ASCII_SIZE] = {0};

  

    // Построить массив подсчета символов из ввода

    // строка.

    int len = strlen(str);

    int max = 0;  // Инициализировать максимальное количество

    char result;   // Инициализировать результат

  

    // Обход строки и ведение

    // количество каждого символа

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

        count[str[i]]++;

        if (max < count[str[i]]) {

            max = count[str[i]];

            result = str[i];

        }

    }

  

    return result;

}

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

int main()

{

    char str[] = "sample string";

    cout << "Max occurring character is "

         << getMaxOccuringChar(str);

}

Джава

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

  

public class GFG 

{

    static final int ASCII_SIZE = 256;

    static char getMaxOccuringChar(String str)

    {

        // Создать массив для подсчета отдельных

        // символы и инициализируем массив как 0

        int count[] = new int[ASCII_SIZE];

       

        // Построить массив подсчета символов из ввода

        // строка.

        int len = str.length();

        for (int i=0; i<len; i++)

            count[str.charAt(i)]++;

       

        int max = -1// Инициализировать максимальное количество

        char result = ' ';   // Инициализировать результат

       

        // Обход строки и ведение

        // количество каждого символа

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

            if (max < count[str.charAt(i)]) {

                max = count[str.charAt(i)];

                result = str.charAt(i);

            }

        }

       

        return result;

    }

      

    // Метод драйвера

    public static void main(String[] args)

    {

        String str = "sample string";

        System.out.println("Max occurring character is " +

                            getMaxOccuringChar(str));

    }

}

питон

# Python программа для возврата максимального встречающегося символа во входной строке

ASCII_SIZE = 256

  

def getMaxOccuringChar(str):

    # Создать массив для хранения количества отдельных символов

    # Инициализировать массив count в ноль

    count = [0] * ASCII_SIZE

  

    # Служебные переменные

    max = -1

    c = ''

  

    # Обход строки и ведение счета

    # каждый символ

    for i in str:

        count[ord(i)]+=1;

  

    for i in str:

        if max < count[ord(i)]:

            max = count[ord(i)]

            c = i

  

    return c

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

str = "sample string"

print "Max occurring character is " + getMaxOccuringChar(str)

  
# Хотя эта программа может быть написана не более чем в 3 строки на Python
# вышеуказанная программа была написана для лучшего понимания
# читатель

  
# Укороченная версия программы
# импорт коллекций
# str = "образец строки"
# печать "Максимальный встречающийся символ" +
# collection.Counter (str) .most_common (1) [0] [0]

  
# Этот код предоставлен Bhavya Jain

C #

// C # программа для вывода максимума
// встречающийся символ в строке

using System;

  

class GFG

{

    static int ASCII_SIZE = 256;

      

    static char getMaxOccuringChar(String str)

    {

        // Создать массив, чтобы вести подсчет

        // отдельные символы и

        // инициализируем массив как 0

        int []count = new int[ASCII_SIZE];

      

        // Построить массив символов

        // из входной строки.

        int len = str.Length;

        for (int i = 0; i < len; i++)

            count[str[i]]++;

      

        int max = -1; // Инициализировать максимальное количество

        char result = ' '; // Инициализировать результат

      

        // Обход строки и

        // ведение счета каждого персонажа

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

            if (max < count[str[i]]) {

                max = count[str[i]];

                result = str[i];

            }

        }

      

        return result;

    }

      

    // Метод драйвера

    public static void Main()

    {

        String str = "sample string";

        Console.Write("Max occurring character is " +

                            getMaxOccuringChar(str));

    }

}

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

PHP

<?php 
// PHP программа для вывода максимума
// встречающийся символ в строке

$ASCII_SIZE = 256; 

  

function getMaxOccuringChar($str

    global $ASCII_SIZE

      

    // Создать массив для подсчета

    // отдельных персонажей и

    // инициализируем массив как 0

    $count = array_fill(0, $ASCII_SIZE, NULL); 

  

    // Построить массив символов

    // из входной строки.

    $len = strlen($str); 

    $max = 0; // Инициализировать максимальное количество

  

    // Обход строки

    // и ведение счета

    // каждый символ

    for ($i = 0; $i < ($len); $i++) 

    

        $count[ord($str[$i])]++; 

        if ($max < $count[ord($str[$i])]) 

        

            $max = $count[ord($str[$i])]; 

            $result = $str[$i]; 

        

    

  

    return $result

  
// Код драйвера

$str = "sample string"

echo "Max occurring character is "

           getMaxOccuringChar($str); 

              
// Этот код предоставлен ita_c
?> 

Выход:

Max occurring character is s

Сложность времени: O (n)
Сложность пространства: O (1) — потому что мы используем фиксированное пространство (массив Hash) независимо от размера входной строки.

Примечания:
Если более одного символа имеют одинаковое количество и это число максимальное, функция возвращает первый символ с максимальным количеством во входной строке. Например, если входной строкой является «тестовая выборка», то есть три символа с одинаковым и максимальным количеством двух, т.е. «t», «e» и «s», но наша программа выдаст «t», потому что «t» стоит на первом месте во входной строке , Аналогично, вывод для «cbbbbccc» будет «c».

Как вариант вышеупомянутой программы, подумайте об изменении в коде, если вы хотите вывести «e» для ввода «тестового образца», то есть символ максимального числа, и этот символ должен иметь наименьшее значение ASCII. Для «cbbbbccc» вывод должен быть «b». Попробуйте!

Кроме того, можете ли вы подумать об улучшении, если мы сможем избежать двух циклов в приведенном выше? По сути, вам нужно выяснить, можем ли мы решить ту же проблему с помощью одного цикла вместо двух.

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

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

Возврат максимального встречающегося символа во входной строке

0.00 (0%) 0 votes