Strängar är ett mycket viktigt ämne i programmeringsintervjuer. Det är klokt att öva på några programmeringsproblem fokuserade på strängar innan dina intervjuer. I den här artikeln får du lära dig hur du hittar det vanligaste tecknet i en sträng.
Exempel för att förstå problemet
Exempel 1: Låt den givna strängen vara “Makeuseof”. Tecknet “e” förekommer 2 gånger i den givna strängen och alla andra tecken förekommer endast en gång. Således har tecknet ‘e’ den högsta frekvensen i den givna strängen.
Exempel 2: Låt den givna strängen vara “Hon ser ost”. Tecknet ‘e’ förekommer 6 gånger i den givna strängen och alla andra tecken förekommer mindre än 6 gånger. Således har tecknet ‘e’ den högsta frekvensen i den givna strängen.
Metod för att hitta den vanligast förekommande karaktären i en sträng
Hashingtekniken är det mest effektiva sättet att hitta det tecken som har den högsta frekvensen i en sträng. I den här tekniken korsas strängen och varje tecken i strängen hashas till en array av ASCII-tecken.
Låt inmatningssträngen vara “Makeuseof”, varje tecken i denna sträng hashas enligt följande:
frekvens[‘M’] = 1
frekvens[‘a] = 1
frekvens[‘k’] = 1
frekvens[‘e’] = 2
frekvens[‘u’] = 1
frekvens[‘s’] = 1
frekvens[‘o’] = 1
frekvens[‘f’] = 1
Indexet för det maximala värdet i frekvensmatrisen returneras. Här 2 är det högsta värdet, därför returneras ‘e’.
C++-program för att hitta karaktären med den högsta frekvensen
Nedan är programmet C++ för att hitta tecknet med den högsta frekvensen i en sträng:
// 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;
}
Produktion:
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-program för att hitta karaktären med den högsta frekvensen
Nedan finns Python-programmet för att hitta tecknet med högst frekvens i en sträng:
# 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))
Produktion:
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 Program för att hitta karaktären med den högsta frekvensen
Nedan är C-programmet för att hitta tecknet med högst frekvens i en sträng:
// 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));
}
Produktion:
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-program för att hitta karaktären med den högsta frekvensen
Nedan finns JavaScript-programmet för att hitta tecknet med högst frekvens i en sträng:
// 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>")
Produktion:
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
Analysera komplexiteten i tid och rum
Tidskomplexiteten hos maxFrequencyChar() funktion är På). Rymdens komplexitet maxFrequencyChar() funktion är O(1) som ett fast utrymme (hash-array). Det beror inte på storleken på inmatningssträngen.
Big-O notation ger dig ett sätt att beräkna hur lång tid det tar att köra din kod. Det är ett av de viktigaste koncepten för analys av algoritmer. Om du är en programmerare måste du känna till Big-O Notation.
Om författaren
Yuvraj Chandra (80 artiklar publicerade)
Yuvraj är en datavetenskapsstudent vid University of Delhi, Indien. Han brinner för Full Stack Web Development. När han inte skriver undersöker han djupet i olika teknologier.
Mer från Yuvraj Chandra
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
