ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และจำนวนเต็มสองจำนวน a และ b ภารกิจของเราคือ หาองค์ประกอบที่ปรากฏ b ครั้งเพียงอย่างเดียว
ค่าทั้งหมดของอาร์เรย์เกิดขึ้น a ครั้ง ยกเว้นค่าหนึ่งซึ่งเกิดขึ้น b ครั้งในอาร์เรย์ และเราต้องหาค่านั้น
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3
เอาต์พุต
5
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการนับจำนวนครั้งที่แต่ละองค์ประกอบเกิดขึ้นแล้วเก็บในเมทริกซ์ 2 มิติ จากนั้นเดินทางผ่านเมทริกซ์เพื่อหาค่าที่มีความถี่ b
ความซับซ้อนของเวลาของวิธีนี้คือ O(N2) แต่วิธีที่มีประสิทธิภาพมากกว่าที่สามารถแก้ปัญหาได้คือการหาผลรวมขององค์ประกอบที่ไม่ซ้ำกันทั้งหมดของอาร์เรย์แล้วคูณด้วย a จากนั้นลบผลรวมของอาร์เรย์ทั้งหมดออกจากค่านี้แล้วหารผลลัพธ์ด้วย (a-b) ค่าที่ได้คือค่าที่มีความถี่ b
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <bits/stdc++.h> using namespace std; int findbFreqVal(int arr[], int n, int a, int b){ unordered_set<int> uniqueVal; int uniqueValSum = 0, arrSum = 0; for (int i = 0; i < n; i++) { if (uniqueVal.find(arr[i]) == uniqueVal.end()) { uniqueVal.insert(arr[i]); uniqueValSum += arr[i]; } arrSum += arr[i]; } uniqueValSum = a * uniqueValSum; return ((uniqueValSum - arrSum) / (a - b)); } int main(){ int arr[] = { 4, 4, 4, 31, 8, 8, 8, 5, 5, 5}; int a = 3, b = 1; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The value of the array that appears b times is "<<findbFreqVal(arr, n, a, b); return 0; }
เอาต์พุต
The value of the array that appears b times is 31
