Trong bài toán này, chúng ta được cung cấp một arr [] có kích thước n và hai số nguyên a và b. Nhiệm vụ của chúng tôi là f ind là phần tử duy nhất xuất hiện lần b .
Tất cả các giá trị của mảng xuất hiện một lần ngoại trừ một giá trị xuất hiện b lần trong mảng và chúng ta cần tìm giá trị đó.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3 Đầu ra
5
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là đếm sự xuất hiện của từng phần tử và sau đó lưu trữ nó trong ma trận 2D. Sau đó duyệt qua ma trận để tìm giá trị có tần suất xuất hiện b.
Độ phức tạp về thời gian của phương pháp này là O (N 2 ) nhưng một cách tiếp cận hiệu quả hơn có thể giải quyết vấn đề là tìm tổng của tất cả các phần tử duy nhất của mảng và sau đó nhân nó với a. Sau đó, trừ tổng của toàn mảng với giá trị này và sau đó chia kết quả cho (a-b). Giá trị kết quả là giá trị có tần suất xuất hiện là b.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The value of the array that appears b times is 31