使用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

更新於:2022年2月11日

101 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告