So finden Sie das am häufigsten vorkommende Zeichen in einer Zeichenfolge

Eskere Guru

Strings sind ein sehr wichtiges Thema bei der Programmierung von Interviews. Es ist ratsam, vor Ihren Interviews einige Programmierprobleme zu üben, die sich auf Strings konzentrieren. In diesem Artikel erfahren Sie, wie Sie das am häufigsten vorkommende Zeichen in einer Zeichenfolge finden.

Beispiele zum Verständnis des Problems

Beispiel 1 : Der angegebene String sei "Makeuseof". Das Zeichen 'e' kommt in der angegebenen Zeichenfolge 2 Mal vor und alle anderen Zeichen kommen nur einmal vor. Somit hat das Zeichen 'e' die höchste Häufigkeit in der gegebenen Zeichenfolge.

Beispiel 2 : Die angegebene Zeichenfolge sei "Sie sieht Käse". Das Zeichen 'e' kommt in der angegebenen Zeichenfolge 6-mal vor und alle anderen Zeichen kommen weniger als 6-mal vor. Somit hat das Zeichen 'e' die höchste Häufigkeit in der gegebenen Zeichenfolge.

Vorgehensweise, um das am häufigsten vorkommende Zeichen in einer Zeichenfolge zu finden

Die Hashing-Technik ist die effizienteste Methode, um das Zeichen mit der höchsten Häufigkeit in einer Zeichenfolge zu finden. Bei dieser Technik wird die Zeichenfolge durchlaufen und jedes Zeichen der Zeichenfolge wird in ein Array von ASCII-Zeichen gehasht.

Lassen Sie die Eingabezeichenfolge "Makeuseof" sein, jedes Zeichen dieser Zeichenfolge wird wie folgt gehasht:

Frequenz['M'] = 1

Frequenz['a] = 1

Frequenz['k'] = 1

Frequenz['e'] = 2

Frequenz['u'] = 1

Frequenz['s'] = 1

Frequenz['o'] = 1

Frequenz['f'] = 1

Der Index des Maximalwerts im Frequenz-Array wird zurückgegeben. Hier ist 2 der höchste Wert, daher wird 'e' zurückgegeben.

C++-Programm zum Finden des Zeichens mit der höchsten Häufigkeit

Unten ist das C++-Programm, um das Zeichen mit der höchsten Häufigkeit in einer Zeichenfolge zu finden:

Verwandte: So zählen Sie die Vorkommen eines bestimmten Zeichens in einer Zeichenfolge

 // C++ program to find the character
 // having the highest frequency in a string
 #include <iostream>
 #include <string>
 #define ASCII_SIZE 256
 using namespace std;
 char maxFrequencyChar(string str)
 {
 // Array to store frequency of each characters
 // Initialized the frequency of each character as 0
 int frequency[ASCII_SIZE] = {0};
 // Finding length of the input string
 int lenOfStr = str.length();
 // Initialize maxFrequency variable
 int maxFrequency = -1;
 // Initialize maxFrequencyChar variable
 char maxFrequencyChar;
 // Traversing and maintaining the
 // frequency of each characters
 for (int i = 0; i < lenOfStr; i++)
 {
 frequency[str[i]]++;
 if (maxFrequency < frequency[str[i]])
 {
 maxFrequency = frequency[str[i]];
 maxFrequencyChar = str[i];
 }
 }
 return maxFrequencyChar;
 }
 // Driver Code
 int main()
 {
 string str1 = "Which witch is which?";
 cout << "str1: " << str1 << endl;
 cout << "The highest frequency character is: " << maxFrequencyChar(str1) << endl;
 string str2 = "He threw three free throws";
 cout << "str2: " << str2 << endl;
 cout << "The highest frequency character is: " << maxFrequencyChar(str2) << endl;
 string str3 = "Eddie edited it";
 cout << "str3: " << str3 << endl;
 cout << "The highest frequency character is: " << maxFrequencyChar(str3) << endl;
 string str4 = "Makeuseof";
 cout << "str4: " << str4 << endl;
 cout << "The highest frequency character is: " << maxFrequencyChar(str4) << endl;
 string str5 = "She sees cheese";
 cout << "str5: " << str5 << endl;
 cout << "The highest frequency character is: " << maxFrequencyChar(str5) << endl;
 }

Ausgabe:

 str1: Which witch is which?
 The highest frequency character is: h
 str2: He threw three free throws
 The highest frequency character is: e
 str3: Eddie edited it
 The highest frequency character is: d
 str4: Makeuseof
 The highest frequency character is: e
 str5: She sees cheese
 The highest frequency character is: e

Python-Programm zum Finden des Zeichens mit der höchsten Häufigkeit

Unten ist das Python-Programm, um das Zeichen mit der höchsten Häufigkeit in einer Zeichenfolge zu finden:

Verwandte: Wie man einen String in C++, Python und JavaScript umkehrt

 # Python program to find the character
 # having the highest frequency in a string
 ASCII_SIZE = 256
 def maxFrequencyChar(str):
 # Array to store frequency of each characters
 # Initialized the frequency of each character as 0
 frequency = [0] * ASCII_SIZE
 # Initialize maxFrequency variable
 maxFrequency = -1
 # Initialize maxFrequencyChar variable
 maxFrequencyChar = ''
 # Traversing and maintaining the
 # frequency of each characters
 for i in str:
 frequency[ord(i)] += 1
 for i in str:
 if maxFrequency < frequency[ord(i)]:
 maxFrequency = frequency[ord(i)]
 maxFrequencyChar = i
 return maxFrequencyChar
 # Driver Code
 str1 = "Which witch is which?"
 print("str1:", str1)
 print("The highest frequency character is:", maxFrequencyChar(str1))
 str2 = "He threw three free throws"
 print("str2:", str2)
 print("The highest frequency character is:", maxFrequencyChar(str2))
 str3 = "Eddie edited it"
 print("str3:", str3)
 print("The highest frequency character is:", maxFrequencyChar(str3))
 str4 = "Makeuseof"
 print("str4:", str4)
 print("The highest frequency character is:", maxFrequencyChar(str4))
 str5 = "She sees cheese"
 print("str5:", str5)
 print("The highest frequency character is:", maxFrequencyChar(str5))

Ausgabe:

 str1: Which witch is which?
 The highest frequency character is: h
 str2: He threw three free throws
 The highest frequency character is: e
 str3: Eddie edited it
 The highest frequency character is: d
 str4: Makeuseof
 The highest frequency character is: e
 str5: She sees cheese
 The highest frequency character is: e

C-Programm zum Finden des Zeichens mit der höchsten Häufigkeit

Unten ist das C-Programm, um das Zeichen mit der höchsten Häufigkeit in einer Zeichenfolge zu finden:

Verwandte: So finden Sie Vokale, Konsonanten, Ziffern und Sonderzeichen in einer Zeichenfolge

 // C program to find the character
 // having the highest frequency in a string
 #include <iostream>
 #include <cstring>
 #define ASCII_SIZE 256
 using namespace std;
 char maxFrequencyChar(char *str)
 {
 // Array to store frequency of each characters
 // Initialized the frequency of each character as 0
 int frequency[ASCII_SIZE] = {0};
 // Finding length of the input string
 int lenOfStr = strlen(str);
 // Initialize maxFrequency variable
 int maxFrequency = 0;
 // Initialize maxFrequencyChar variable
 char maxFrequencyChar;
 // Traversing and maintaining the
 // frequency of each characters
 for (int i = 0; i < lenOfStr; i++)
 {
 frequency[str[i]]++;
 if (maxFrequency < frequency[str[i]])
 {
 maxFrequency = frequency[str[i]];
 maxFrequencyChar = str[i];
 }
 }
 return maxFrequencyChar;
 }
 // Driver Code
 int main()
 {
 char str1[] = "Which witch is which?";
 printf("str1: %s", str1);
 printf("The highest frequency character is: %c ⁠n", maxFrequencyChar(str1));
 char str2[] = "He threw three free throws";
 printf("str2: %s", str2);
 printf("The highest frequency character is: %c ⁠n", maxFrequencyChar(str2));
 char str3[] = "Eddie edited it";
 printf("str3: %s", str3);
 printf("The highest frequency character is: %c ⁠n", maxFrequencyChar(str3));
 char str4[] = "Makeuseof";
 printf("str4: %s", str4);
 printf("The highest frequency character is: %c ⁠n", maxFrequencyChar(str4));
 char str5[] = "She sees cheese";
 printf("str1: %s", str5);
 printf("The highest frequency character is: %c ⁠n", maxFrequencyChar(str5));
 }

Ausgabe:

 str1: Which witch is which?
 The highest frequency character is: h
 str2: He threw three free throws
 The highest frequency character is: e
 str3: Eddie edited it
 The highest frequency character is: d
 str4: Makeuseof
 The highest frequency character is: e
 str5: She sees cheese
 The highest frequency character is: e

JavaScript-Programm zum Finden des Zeichens mit der höchsten Häufigkeit

Unten ist das JavaScript-Programm, um das Zeichen mit der höchsten Häufigkeit in einer Zeichenfolge zu finden:

 // JavaScript program to find the character
 // having the highest frequency in a string
 let ASCII_SIZE = 256;
 function maxFrequencyChar(str)
 {
 // Array to store frequency of each characters
 // Initialized the frequency of each character as 0
 let frequency = new Array(ASCII_SIZE);
 for (let i = 0; i < ASCII_SIZE; i++)
 {
 frequency[i] = 0;
 }
 // Finding length of the input string
 let lenOfStr = str.length;
 for (let i = 0; i < lenOfStr; i++)
 {
 frequency[str[i].charCodeAt(0)] += 1;
 }
 // Initialize maxFrequency variable
 let maxFrequency = -1;
 // Initialize maxFrequencyChar variable
 let maxFrequencyChar = '';
 // Traversing and maintaining the
 // frequency of each characters
 for (let i = 0; i < lenOfStr; i++)
 {
 if (maxFrequency < frequency[str[i].charCodeAt(0)])
 {
 maxFrequency = frequency[str[i].charCodeAt(0)];
 maxFrequencyChar = str[i];
 }
 }
 return maxFrequencyChar;
 }
 // Driver Code
 let str1 = "Which witch is which?";
 document.write("str1: " + str1 + "<br>");
 document.write("The highest frequency character is: " + maxFrequencyChar(str1) + "<br>")
 let str2 = "He threw three free throws";
 document.write("str2: " + str2 + "<br>");
 document.write("The highest frequency character is: " + maxFrequencyChar(str2) + "<br>")
 let str3 = "Eddie edited it";
 document.write("str3: " + str3 + "<br>");
 document.write("The highest frequency character is: " + maxFrequencyChar(str3) + "<br>")
 let str4 = "Makeuseof";
 document.write("str4: " + str4 + "<br>");
 document.write("The highest frequency character is: " + maxFrequencyChar(str4) + "<br>")
 let str5 = "She sees cheese";
 document.write("str5: " + str5 + "<br>");
 document.write("The highest frequency character is: " + maxFrequencyChar(str5) + "<br>")

Ausgabe:

 str1: Which witch is which?
 The highest frequency character is: h
 str2: He threw three free throws
 The highest frequency character is: e
 str3: Eddie edited it
 The highest frequency character is: d
 str4: Makeuseof
 The highest frequency character is: e
 str5: She sees cheese
 The highest frequency character is: e

Analysieren Sie die Zeit- und Raumkomplexität

Die Zeitkomplexität der Funktion maxFrequencyChar() beträgt O(n) . Die Raumkomplexität der Funktion maxFrequencyChar() ist O(1) als fester Raum (Hash-Array). Es hängt nicht von der Größe der Eingabezeichenfolge ab.

Mit der Big-O-Notation können Sie berechnen, wie lange es dauert, Ihren Code auszuführen. Es ist eines der wichtigsten Konzepte für die Analyse von Algorithmen. Wenn Sie ein Programmierer sind, müssen Sie die Big-O-Notation kennen.