使用C++查詢只出現b次的元素
在這個問題中,我們得到一個大小為n的陣列arr[]和兩個整數a和b。我們的任務是找到只出現b次的元素。
陣列的所有值都出現a次,只有一個值出現b次,我們需要找到那個值。
讓我們來看一個例子來理解這個問題:
輸入
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3
輸出
5
解決方案
一個簡單的解決方案是透過計算每個元素的出現次數,然後將其儲存在二維矩陣中。然後遍歷矩陣以查找出現頻率為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
廣告