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

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

ตัวอย่างอินพุต 1

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

เอาต์พุต

คำอธิบาย

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

ตัวอย่างอินพุต 2

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

เอาต์พุต

1 หรือ 4

คำอธิบาย

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

วิธีการแก้ปัญหา

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

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

รับอินพุตอาร์เรย์ขนาด N
ฟังก์ชัน Integer maxOccurrence(int A[], int size) รับอาร์เรย์และขนาดเป็นอินพุตและคืนค่าตัวเลขที่มีความถี่สูงสุด
สร้าง hashmap ของทุกองค์ประกอบของอาร์เรย์โดยใช้ key เป็นองค์ประกอบและ value เป็นความถี่ของมัน
วนลูปผ่าน map และตรวจสอบว่ามีองค์ประกอบใดที่มีความถี่มากที่สุด แล้วคืนค่าผลลัพธ์เป็นตัวเลข มิฉะนั้นถ้าไม่มีตัวเลขใดในอาร์เรย์ ให้คืนค่า '-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 มีความถี่ 3 ซึ่งเป็นความถี่สูงสุดจากตัวเลขอื่นๆ ทั้งหมดในอาร์เรย์ที่กำหนด