เขียนโปรแกรมในภาษา C++ เพื่อค้นหาองค์ประกอบที่พบบ่อยที่สุดในอาร์เรย์ของจำนวนเต็มที่กำหนด

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มขนาด N ภารกิจคือการค้นหาองค์ประกอบที่มีความถี่มากที่สุดในอาร์เรย์ของจำนวนเต็มที่กำหนด ตัวอย่างเช่น

อินพุต-1 −

N = 8
A[ ] = {1,2,4,3,3,1,1,5}

ผลผลิต −

1

คำอธิบาย − ในอาร์เรย์ของจำนวนเต็มที่กำหนด จำนวนที่ปรากฏมากที่สุดคือ '1' ดังนั้นผลลัพธ์ที่ได้คือ '1'

อินพุต-2 −

N = 6
A[ ] = {1,4,4,4,1,1}

ผลลัพธ์-a −

1

ผลลัพธ์-b −

4

คำอธิบาย:ในอาร์เรย์ของจำนวนเต็มที่กำหนด จำนวนที่ปรากฏมากที่สุดคือ '1' และ '4' ดังนั้นเราจึงสามารถส่งคืนผลลัพธ์ไปยังรายการใดรายการหนึ่งได้

แนวทางการแก้ปัญหานี้

อาร์เรย์ที่ระบุมีจำนวนเต็มหลายจำนวนซึ่งเราต้องหาองค์ประกอบที่มีความถี่มากที่สุดในอาร์เรย์ ในการแก้ปัญหานี้ในเวลาเชิงเส้น O(n) และลิเนียร์สเปซ O(n) เราสามารถใช้แนวทางของแฮชแมปได้

ในแนวทางนี้ เราจะสร้าง unordered map (STL Library) ซึ่งประกอบด้วยคู่คีย์-ค่า ซึ่งคีย์จะเป็นองค์ประกอบ และ Value จะเป็นองค์ประกอบที่เกิดขึ้น ขณะสำรวจผ่านแผนที่ เราจะพบจำนวนการเกิดขึ้นสูงสุดและส่งคืนตัวเลขเป็นผลลัพธ์

• รับอินพุตอาร์เรย์ขนาด N.

• ฟังก์ชัน Integer maxOccurrence(int A[], int size) รับอาร์เรย์และขนาดเป็นอินพุตและส่งกลับตัวเลขที่มีความถี่สูงสุด

• การสร้าง hashmap ขององค์ประกอบทั้งหมดของอาร์เรย์โดยใช้คีย์เป็นองค์ประกอบและค่าเป็นความถี่

• วนซ้ำบนแผนที่และตรวจสอบว่าองค์ประกอบใดที่มีความถี่มากที่สุดแล้วส่งคืนผลลัพธ์เป็นตัวเลข มิฉะนั้น หากไม่มีตัวเลขอยู่ในอาร์เรย์ ให้คืนค่า '-1'

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
int maxOccurrence(int A[], int size){
   int mxcount=0;
   int res=-1;
   unordered_map<int,int>mp;
   for(int i=0;i<size;i++){
      mp[A[i]]++;
   }
   for(auto x:mp){
      if(x.second>mxcount){
         res= x.first;
         mxcount=x.second;
      }
   }
   return res;
}
int main(){
   int N=6;
   int A[N]= {1,4,4,4,2,1};
   int ans= maxOccurrence(A,N);
   cout<<ans<<endl;
   return 0;
}

ผลลัพธ์

หากเราจะเรียกใช้โค้ดข้างต้น มันจะพิมพ์ผลลัพธ์เป็น,

4

4 มีความถี่เท่ากับ 3 ซึ่งเป็นความถี่สูงสุดจากตัวเลขอื่นๆ ทั้งหมดในอาร์เรย์ที่กำหนด