Jak znaleźć najczęściej występujący znak w ciągu?

Struny są bardzo ważnym tematem w wywiadach programistycznych. Rozsądnie jest przećwiczyć pewne problemy z programowaniem skupione na strunach przed rozmowami kwalifikacyjnymi. W tym artykule dowiesz się, jak znaleźć najczęściej występujący znak w ciągu.

Przykłady zrozumienia problemu

Przykład 1: Niech podany ciąg będzie „Makeuseof”. Znak 'e' występuje w danym ciągu 2 razy, a wszystkie inne znaki występują tylko raz. Tak więc znak 'e' ma najwyższą częstotliwość w danym ciągu.

Przykład 2: Niech podany ciąg to "Ona widzi ser". Znak 'e' występuje w danym ciągu 6 razy, a wszystkie pozostałe znaki występują mniej niż 6 razy. Tak więc znak 'e' ma najwyższą częstotliwość w danym ciągu.

Podejście do znalezienia najczęściej występującego znaku w ciągu

Technika mieszania jest najskuteczniejszym sposobem na znalezienie znaku o najwyższej częstotliwości w łańcuchu. W tej technice ciąg jest przeszukiwany, a każdy znak ciągu jest mieszany w tablicę znaków ASCII.

Niech ciąg wejściowy to „Makeuseof”, każdy znak tego ciągu jest haszowany w następujący sposób:

częstotliwość['M'] = 1

częstotliwość['a] = 1

częstotliwość['k'] = 1

częstotliwość['e'] = 2

częstotliwość['u'] = 1

częstotliwość ['s'] = 1

częstotliwość['o'] = 1

częstotliwość['f'] = 1

Zwracany jest indeks maksymalnej wartości w tablicy częstotliwości. Tutaj 2 jest najwyższą wartością, dlatego zwracane jest 'e'.

Program C++ do znajdowania postaci z najwyższą częstotliwością

Poniżej znajduje się program C++ do znalezienia znaku o największej częstotliwości w ciągu:

Związane z: Jak policzyć wystąpienia danego znaku w ciągu?

// program C++ do znalezienia znaku the
// posiadające najwyższą częstotliwość w łańcuchu
#zawierać 
#zawierać 
#define ASCII_SIZE 256
używając standardowej przestrzeni nazw;
char maxFrequencyChar (ciąg znaków)
{
// Tablica do przechowywania częstotliwości każdego znaku
// Zainicjuj częstotliwość każdego znaku jako 0
int częstotliwość[ASCII_SIZE] = {0};
// Znajdowanie długości ciągu wejściowego
int lenOfStr = str.długość();
// Zainicjuj zmienną maxFrequency
int maxCzęstotliwość = -1;
// Zainicjuj zmienną maxFrequencyChar
char maxCzęstotliwośćChar;
// Przemierzanie i utrzymywanie
// częstotliwość każdego znaku
dla (int i = 0; i < lenOfStr; i++)
{
częstotliwość[str[i]]++;
if (maxCzęstotliwość < częstotliwość[str[i]])
{
maxFrequency = częstotliwość[str[i]];
maxCzęstotliwośćChar = str[i];
}
}
zwróć maxFrequencyChar;
}
// Kod kierowcy
int main()
{
string str1 = "Która wiedźma jest którą?";
cout << "str1: " << str1 << endl;
cout << "Znakiem o najwyższej częstotliwości jest: " << maxFrequencyChar (str1) << endl;
string str2 = "Rzucił trzy rzuty wolne";
cout << "str2: " << str2 << endl;
cout << "Znakiem o najwyższej częstotliwości jest: " << maxFrequencyChar (str2) << endl;
string str3 = "Edytował to Eddie";
cout << "str3: " << str3 << endl;
cout << "Znakiem o najwyższej częstotliwości jest: " << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4: " << str4 << endl;
cout << "Znakiem o najwyższej częstotliwości jest: " << maxFrequencyChar (str4) << endl;
string str5 = "Ona widzi ser";
cout << "str5: " << str5 << endl;
cout << "Znak o najwyższej częstotliwości to: " << maxFrequencyChar (str5) << endl;
}

Wynik:

str1: Która czarownica jest którą?
Znak o najwyższej częstotliwości to: h
str2: Rzucił trzy rzuty wolne
Znak o najwyższej częstotliwości to: e
str3: Eddie go edytował
Znak o najwyższej częstotliwości to: d
str4: Makeuseof
Znak o najwyższej częstotliwości to: e
str5: Widzi ser
Znak o najwyższej częstotliwości to: e

Program Pythona do znajdowania postaci z najwyższą częstotliwością

Poniżej znajduje się program Pythona do znalezienia znaku o największej częstotliwości w ciągu:

Związane z: Jak odwrócić ciąg znaków w C++, Pythonie i JavaScript

# Program w Pythonie do znalezienia znaku
# posiadające najwyższą częstotliwość w strunie
ASCII_SIZE = 256
def maxCzęstotliwośćChar (str):
# Tablica do przechowywania częstotliwości każdego znaku
# Zainicjuj częstotliwość każdego znaku jako 0
częstotliwość = [0] * ASCII_SIZE
# Zainicjuj zmienną maxFrequency
maksymalna częstotliwość = -1
# Zainicjuj zmienną maxFrequencyChar
maxCzęstotliwośćChar = ''
# Przemierzanie i utrzymywanie
# częstotliwość każdego znaku
dla mnie w ul:
częstotliwość[lub (i)] += 1
dla mnie w ul:
jeśli maxFrequency < częstotliwość[ord (i)]:
maxFrequency = częstotliwość[lub (i)]
maxCzęstotliwośćChar = i
zwróć maxFrequencyChar
# Kod kierowcy
str1 = "Która czarownica jest która?"
print("sł1:", słowo1)
print("Najwyższy znak częstotliwości to:", maxFrequencyChar (str1))
str2 = "Rzucił trzy rzuty wolne"
print("str2:", str2)
print("Najwyższy znak częstotliwości to:", maxFrequencyChar (str2))
str3 = "Edytował to Eddie"
print("str3:", str3)
print("Najwyższy znak częstotliwości to:", maxFrequencyChar (str3))
str4 = "Makeuseof"
print("str4:", str4)
print("Najwyższy znak częstotliwości to:", maxFrequencyChar (str4))
str5 = "Ona widzi ser"
print("str5:", str5)
print("Najwyższy znak częstotliwości to:", maxFrequencyChar (str5))

Wynik:

str1: Która czarownica jest którą?
Znak o najwyższej częstotliwości to: h
str2: Rzucił trzy rzuty wolne
Znak o najwyższej częstotliwości to: e
str3: Eddie go edytował
Znak o najwyższej częstotliwości to: d
str4: Makeuseof
Znak o najwyższej częstotliwości to: e
str5: Widzi ser
Znak o najwyższej częstotliwości to: e

Program C do znajdowania postaci o najwyższej częstotliwości

Poniżej znajduje się program w C do znalezienia znaku o największej częstotliwości w łańcuchu:

Związane z: Jak znaleźć samogłoski, spółgłoski, cyfry i znaki specjalne w ciągu?

// Program C do znalezienia znaku
// posiadające najwyższą częstotliwość w łańcuchu
#zawierać 
#zawierać 
#define ASCII_SIZE 256
używając standardowej przestrzeni nazw;
char maxFrequencyChar (char *str)
{
// Tablica do przechowywania częstotliwości każdego znaku
// Zainicjuj częstotliwość każdego znaku jako 0
int częstotliwość[ASCII_SIZE] = {0};
// Znajdowanie długości ciągu wejściowego
int lenOfStr = strlen (str);
// Zainicjuj zmienną maxFrequency
int maxCzęstotliwość = 0;
// Zainicjuj zmienną maxFrequencyChar
char maxCzęstotliwośćChar;
// Przemierzanie i utrzymywanie
// częstotliwość każdego znaku
dla (int i = 0; i < lenOfStr; i++)
{
częstotliwość[str[i]]++;
if (maxCzęstotliwość < częstotliwość[str[i]])
{
maxFrequency = częstotliwość[str[i]];
maxCzęstotliwośćChar = str[i];
}
}
zwróć maxFrequencyChar;
}
// Kod kierowcy
int main()
{
char str1[] = "Która czarownica jest która?";
printf("str1: %s", str1);
printf("Najwyższy znak częstotliwości to: %c \⁠n", maxFrequencyChar (str1));
char str2[] ​​= "Rzucił trzy rzuty wolne";
printf("str2: %s", str2);
printf("Najwyższy znak częstotliwości to: %c \⁠n", maxFrequencyChar (str2));
char str3[] = "Edytował to Eddie";
printf("str3: %s", str3);
printf("Najwyższy znak częstotliwości to: %c \⁠n", maxFrequencyChar (str3));
char str4[] = "Przeróbka";
printf("str4: %s", str4);
printf("Najwyższy znak częstotliwości to: %c \⁠n", maxFrequencyChar (str4));
char str5[] = "Ona widzi ser";
printf("str1: %s", str5);
printf("Najwyższy znak częstotliwości to: %c \⁠n", maxFrequencyChar (str5));
}

Wynik:

str1: Która czarownica jest którą?
Znak o najwyższej częstotliwości to: h
str2: Rzucił trzy rzuty wolne
Znak o najwyższej częstotliwości to: e
str3: Eddie go edytował
Znak o najwyższej częstotliwości to: d
str4: Makeuseof
Znak o najwyższej częstotliwości to: e
str5: Widzi ser
Znak o najwyższej częstotliwości to: e

Program JavaScript do wyszukiwania postaci z najwyższą częstotliwością

Poniżej znajduje się program JavaScript do znalezienia znaku o największej częstotliwości w ciągu:

// program JavaScript do znalezienia znaku
// posiadające najwyższą częstotliwość w łańcuchu
niech ASCII_SIZE = 256;
funkcja maxFrequencyChar (str)
{
// Tablica do przechowywania częstotliwości każdego znaku
// Zainicjuj częstotliwość każdego znaku jako 0
let frequency = new Array (ASCII_SIZE);
dla (niech i = 0; i < ROZMIAR_ASCII; i++)
{
częstotliwość[i] = 0;
}
// Znajdowanie długości ciągu wejściowego
niech lenOfStr = str.length;
dla (niech i = 0; i < lenOfStr; i++)
{
częstotliwość[str[i].charCodeAt (0)] += 1;
}
// Zainicjuj zmienną maxFrequency
niech maxCzęstotliwość = -1;
// Zainicjuj zmienną maxFrequencyChar
niech maxFrequencyChar = '';
// Przemierzanie i utrzymywanie
// częstotliwość każdego znaku
dla (niech i = 0; i < lenOfStr; i++)
{
if (maxFrequency < częstotliwość[str[i].charCodeAt (0)])
{
maxFrequency = częstotliwość[str[i].charCodeAt (0)];
maxCzęstotliwośćChar = str[i];
}
}
zwróć maxFrequencyChar;
}
// Kod kierowcy
let str1 = "Która wiedźma jest którą?";
document.write("str1: " + str1 + "
");
document.write("Najwyższy znak częstotliwości to: " + maxFrequencyChar (str1) + "
")
let str2 = "Rzucił trzy rzuty wolne";
document.write("str2: " + str2 + "
");
document.write("Najwyższy znak częstotliwości to: " + maxFrequencyChar (str2) + "
")
niech str3 = "Eddie to edytował";
document.write("str3: " + str3 + "
");
document.write("Najwyższy znak częstotliwości to: " + maxFrequencyChar (str3) + "
")
niech str4 = "Makeuseof";
document.write("str4: " + str4 + "
");
document.write("Najwyższy znak częstotliwości to: " + maxFrequencyChar (str4) + "
")
let str5 = "Ona widzi ser";
document.write("str5: " + str5 + "
");
document.write("Najwyższy znak częstotliwości to: " + maxFrequencyChar (str5) + "
")

Wynik:

str1: Która czarownica jest którą?
Znak o najwyższej częstotliwości to: h
str2: Rzucił trzy rzuty wolne
Znak o najwyższej częstotliwości to: e
str3: Eddie go edytował
Znak o najwyższej częstotliwości to: d
str4: Makeuseof
Znak o najwyższej częstotliwości to: e
str5: Widzi ser
Znak o najwyższej częstotliwości to: e

Przeanalizuj złożoność czasu i przestrzeni

Złożoność czasowa maxCzęstotliwośćChar() funkcja to Na). Złożoność przestrzenna maxCzęstotliwośćChar() funkcja to O(1) jako stała przestrzeń (tablica Hash). Nie zależy to od rozmiaru ciągu wejściowego.

Notacja Big-O pozwala obliczyć, ile czasu zajmie uruchomienie kodu. To jedno z najważniejszych pojęć dotyczących analizy algorytmów. Jeśli jesteś programistą, musisz wiedzieć o notacji Big-O.

Yuvraj Chandra (30 opublikowanych artykułów)

Yuvraj jest studentem informatyki na Uniwersytecie w Delhi w Indiach. Jest pasjonatem Full Stack Web Development. Kiedy nie pisze, bada głębię różnych technologii.

Więcej od Yuvraja Chandra