Рубрики

Программа для поиска второго по частоте персонажа

Строки

По заданной строке найдите второй по частоте символ в ней. Ожидаемая сложность по времени составляет O (n), где n — длина входной строки.

Примеры:

Input: str = "aabababa";
Output: Second most frequent character is 'b'

Input: str = "geeksforgeeks";
Output: Second most frequent character is 'g'

Input: str = "geeksquiz";
Output: Second most frequent character is 'g'
The output can also be any other character with 
count 1 like 'z', 'i'.

Input: str = "abcd";
Output: No Second most frequent character

Простое решение — начать с первого символа, сосчитать его вхождения, затем второй символ и так далее. При подсчете этих случаев следите за максимальными и вторыми максимальными значениями. Временная сложность этого решения составляет O (n 2 ).
Мы можем решить эту проблему за O (n) время, используя массив count с размером, равным 256 (при условии, что символы хранятся в формате ASCII). Ниже приводится реализация подхода.

C ++

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256 

  
// функция CPP для поиска
// второй по частоте характер
// в заданной строке 'str'

char getSecondMostFreq(string str) 

{ 

    // подсчитать количество вхождений каждого символа.

    int count[NO_OF_CHARS] = {0}, i; 

    for (i = 0; str[i]; i++) 

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

  

    // Пройдите через count [] и

    // найти второй по величине элемент.

    int first = 0, second = 0; 

    for (i = 0; i < NO_OF_CHARS; i++) 

    { 

        / * Если текущий элемент меньше

        затем сначала обновите оба

        первый и второй * /

        if (count[i] > count[first]) 

        { 

            second = first; 

            first = i; 

        } 

  

        / * Если count [i] находится между первым

        и второй, затем обновить второй * /

        else if (count[i] > count[second] && 

                count[i] != count[first]) 

            second = i; 

    } 

  

    return second; 

} 

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

int main() 

{ 

    string str = "geeksforgeeks"; 

    char res = getSecondMostFreq(str); 

    if (res != '\0') 

        cout << "Second most frequent char is " << res; 

    else

        cout << "No second most frequent character"; 

    return 0; 

} 

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

С

#include <stdio.h>
#define NO_OF_CHARS 256

  
// функция C, чтобы найти второй по частоте символ
// в заданной строке 'str'

char getSecondMostFreq(char *str)

{

    // подсчитать количество вхождений каждого символа.

    int count[NO_OF_CHARS] = {0}, i;

    for (i=0; str[i]; i++)

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

  

    // Пройдите через count [] и найдите второй по величине элемент.

    int first = 0, second = 0;

    for (i = 0; i < NO_OF_CHARS; i++)

    {

        / * Если текущий элемент меньше первого, обновите оба

          первый и второй * /

        if (count[i] > count[first])

        {

            second = first;

            first = i;

        }

  

        / * Если count [i] находится между первым и вторым, обновите секунду * /

        else if (count[i] > count[second] &&

                 count[i] != count[first])

            second = i;

    }

  

    return second;

}

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

int main()

{

  char str[] = "geeksforgeeks";

  char res = getSecondMostFreq(str);

  if (res != '\0')

     printf("Second most frequent char is %c", res);

  else

     printf("No second most frequent character");

  return 0;

}

Джава

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

public class GFG 

{

    static final int NO_OF_CHARS = 256;

      

    // находит второе наиболее часто встречающееся

    // символ

    static char getSecondMostFreq(String str)

    {

        // подсчитать количество вхождений каждого

        // персонаж.

        int[] count = new int[NO_OF_CHARS];

        int i;

        for (i=0; i< str.length(); i++)

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

       

        // Пройдите через count [] и найдите

        // второй по величине элемент

        int first = 0, second = 0;

        for (i = 0; i < NO_OF_CHARS; i++)

        {

            / * Если текущий элемент меньше чем

            сначала обновите и первое и второе * /

            if (count[i] > count[first])

            {

                second = first;

                first = i;

            }

       

            / * Если count [i] находится между первым и

            второй, затем обновить второй * /

            else if (count[i] > count[second] &&

                     count[i] != count[first])

                second = i;

        }

       

        return (char)second;

    }

       

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

    public static void main(String args[])

    {

      String str = "geeksforgeeks";

      char res = getSecondMostFreq(str);

      if (res != '\0')

         System.out.println("Second most frequent char"+

                                       " is " + res);

      else

         System.out.println("No second most frequent"+

                                       "character");

    }

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

Python 3

# Python 3 Программа для поиска
# второй по частоте характер
# в данной строке

  
# Функция поиска второго
# самый частый персонаж
# в заданной строке 'str'

def getSecondMostFreq(str) :

  

    NO_OF_CHARS = 256

  

    # Инициализировать список счетчиков

    # 256 размер со значением 0

    count = [0] * NO_OF_CHARS

  

    # считать количество вхождений

    # каждого персонажа.

    for i in range(len(str)) :

        count[ord(str[i])] += 1

  

    first, second = 0, 0

  

    # Пройдите через количество []

    # и найдите второй по величине элемент.

    for i in range(NO_OF_CHARS) :

  

        # Если текущий элемент меньше

        # затем сначала обновите оба

        # первое и второе

        if count[i] > count[first] :

  

            second = first

            first = i

  

        # Если число [я] находится между

        # первое и второе

        # затем обновите вторую * /

        elif (count[i] > count[second] and

            count[i] != count[first] ) :

              

            second = i

  

    # возврат символа

    return chr(second)

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

if __name__ == "__main__" :

  

    str = "geeksforgeeks"

      

    # вызов функции

    res = getSecondMostFreq(str)

    if res != '\0' :

        print("Second most frequent char is", res)

    else :

        print("No second most frequent character")

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

C #

// C # Программа для поиска второго по частоте
// символ в данной строке

using System;

  

public class GFG {

      

    static int NO_OF_CHARS = 256;

      

    // находит второе наиболее часто

    // встречающийся символ

    static char getSecondMostFreq(string str)

    {

          

        // подсчитать количество вхождений каждого

        // персонаж.

        int []count = new int[NO_OF_CHARS];

  

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

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

      

        // Пройдите через count [] и найдите

        // второй по величине элемент

        int first = 0, second = 0;

          

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

        {

              

            / * Если текущий элемент меньше

            затем сначала обновите оба

            и второй * /

            if (count[i] > count[first])

            {

                second = first;

                first = i;

            }

      

            / * Если count [i] находится между первым

            и второй, затем обновить второй * /

            else if (count[i] > count[second] &&

                       count[i] != count[first])

                second = i;

        }

      

        return (char)second;

    }

      

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

    public static void Main()

    {

        string str = "geeksforgeeks";

        char res = getSecondMostFreq(str);

          

        if (res != '\0')

            Console.Write("Second most frequent char"+

                                        " is " + res);

        else

            Console.Write("No second most frequent"+

                                        "character");

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php

$NO_OF_CHARS=256; 

  
// PHP функция для поиска
// второй по частоте характер
// в заданной строке 'str'

function getSecondMostFreq($str) 

{ 

    global $NO_OF_CHARS;

      

    // подсчитать количество вхождений каждого символа.

    $count=array_fill(0,$NO_OF_CHARS,0); 

    for ($i = 0; $i < strlen($str); $i++) 

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

  

    // Пройдите через count [] и

    // найти второй по величине элемент.

    $first = $second = 0; 

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

    { 

        / * Если текущий элемент меньше

        затем сначала обновите оба

        первый и второй * /

        if ($count[$i] > $count[$first]) 

        { 

            $second = $first; 

            $first = $i; 

        } 

  

        / * Если count [i] находится между первым

        и второй, затем обновить второй * /

        else if ($count[$i] > $count[$second] && 

                $count[$i] != $count[$first]) 

            $second = $i; 

    } 

  

    return chr($second); 

} 

  

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

    $str = "geeksforgeeks"; 

    $res = getSecondMostFreq($str); 

    if (strlen($res)) 

        echo "Second most frequent char is ".$res; 

    else

        echo "No second most frequent character"; 

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


Выход:

Second most frequent char is g

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

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

Программа для поиска второго по частоте персонажа

0.00 (0%) 0 votes