ในปัญหานี้ เราได้รับสตริงอินพุตของอักขระตัวพิมพ์เล็ก งานของเราคือ m อักขระที่เกิดขึ้นจริงในสตริงอินพุต .
ในกรณีที่มีหลายค่าที่มีความถี่ในการเกิดขึ้นเท่ากัน เราจำเป็นต้องพิมพ์ค่าที่เล็กกว่าพจนานุกรมศัพท์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
string = “programming”
ผลผลิต
g
แนวทางการแก้ปัญหา
ในการหาทางแก้ไขปัญหา เราต้องเรียงลำดับสตริงที่อ่านแล้วสำรวจสตริงเพื่อที่เราจะได้พบอักขระที่มีจำนวนอักขระสูงสุดในสตริง เราจะใช้วิธีแฮช (วิธีตารางแฮช) เพื่อเอาชนะปัญหานี้ การข้ามและแฮชอักขระแต่ละตัวในอาร์เรย์ของอักขระเรียกว่าการแฮช
โดยปกติขนาดอาร์เรย์แฮชจะได้รับการจัดสรรเป็น 256 แต่ถ้าสตริงมีเฉพาะอักขระตั้งแต่ 0 ถึง 127 เราอาจใช้ตารางแฮชขนาด 128 เพื่อให้เราสามารถจัดสรรขนาดตารางแฮชใหม่ตามสตริงได้
อัลกอริทึม
-
อ่านสตริงอินพุต
-
สร้างฟังก์ชันเพื่อคำนวณจำนวนอักขระสูงสุดที่เกิดขึ้นในสตริง
-
สร้างอาร์เรย์เพื่อนับจำนวนอักขระแต่ละตัวและเริ่มต้นอาร์เรย์เป็น 0
-
สร้างอาร์เรย์การนับจำนวนอักขระจากสตริงอินพุต
-
เริ่มต้นการนับและผลลัพธ์สูงสุด
-
ข้ามผ่านสตริงและรักษาจำนวนกันและกัน
-
สุดท้าย ให้หาตัวอักษรที่มีจำนวนสูงสุดแล้วพิมพ์ออกมา
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
char findMaxOccuringChar(char str[]){
int freq[26] = { 0 };
int maxFreq = -1;
char maxFreqChar;
int len = strlen(str);
for (int i = 0; i < len; i++)
freq[str[i] - 'a']++;
for (int i = 0; i < 26; i++)
if (maxFreq < freq[i]) {
maxFreq = freq[i];
maxFreqChar = (char)(i + 'a');
}
return maxFreqChar;
}
int main(){
char str[] = "programming";
cout<<"Maximum occurring character of input string is "<<findMaxOccuringChar(str);
return 0;
} ผลลัพธ์
Maximum occurring character of input string is g
