ในปัญหานี้ เราได้รับสตริงอินพุตของตัวอักษรพิมพ์เล็ก ภารกิจของเราคือ หาตัวอักษรที่เกิดขึ้นมากที่สุดในสตริงอินพุต
ในกรณีที่มีหลายค่าที่มีความถี่การเกิดขึ้นเท่ากัน เราต้องพิมพ์ค่าที่เล็กกว่าในลำดับเล็กซิโคกราฟิก
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
string = “programming”
เอาต์พุต
g
วิธีการแก้ปัญหา
เพื่อหาคำตอบของปัญหา เราต้องจัดเรียงสตริงที่อ่านมาแล้วเดินทางผ่านสตริงเพื่อที่จะหาตัวอักษรที่มีการเกิดขึ้นมากที่สุดในสตริง เราจะใช้วิธีแฮชชิง (hash table method) เพื่อเอาชนะปัญหานี้ การเดินทางและแฮชตัวอักษรแต่ละตัวเข้าไปในอาร์เรย์ของตัวอักษรเรียกว่าแฮชชิง
โดยปกติ ขนาดอาร์เรย์แฮชถูกจัดสรรเป็น 256 แต่ถ้าสตริงมีตัวอักษรอยู่ในช่วง 0 ถึง 127 เราอาจใช้ตารางแฮชขนาด 128 เพื่อที่จะสามารถ deallocate ขนาดตารางแฮชตามสตริงได้
อัลกอริทึม
อ่านสตริงอินพุต
สร้างฟังก์ชันคำนวณตัวอักษรที่เกิดขึ้นมากที่สุดในสตริง
สร้างอาร์เรย์เก็บจำนวนตัวอักษรแต่ละตัวและเริ่มต้นอาร์เรย์เป็น 0
สร้างอาร์เร่ายนับตัวอักษรจากสตริงอินพุต
เริ่มต้น max count และ result
เดินทางผ่านสตริงและรักษาจำนวนของแต่ละตัวอักษร
ในที่สุด หาตัวอักษรที่มีจำนวนสูงสุดและพิมพ์มัน
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#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
