ในปัญหานี้ เราได้รับ arr[] ขนาด n และจำนวนเต็ม a และ b สองจำนวน งานของเราคือ f ระบุองค์ประกอบเดียวที่ปรากฏขึ้น b ครั้ง .
ค่าทั้งหมดของอาร์เรย์เกิดขึ้นในช่วงเวลาหนึ่งยกเว้นค่าหนึ่งซึ่งเกิดขึ้น b ครั้งในอาร์เรย์และเราจำเป็นต้องค้นหาค่านั้น
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3 ผลผลิต
5
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการนับการเกิดขึ้นของแต่ละองค์ประกอบแล้วจัดเก็บไว้ในเมทริกซ์ 2 มิติ จากนั้นข้ามเมทริกซ์เพื่อหาค่าที่มีความถี่การเกิด b.
ความซับซ้อนของเวลาของวิธีนี้คือ O(N 2 ) แต่วิธีที่มีประสิทธิภาพมากกว่าที่สามารถแก้ปัญหาได้คือการหาผลรวมขององค์ประกอบเฉพาะทั้งหมดของอาร์เรย์แล้วคูณด้วย 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
