資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用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 次瀏覽
廣告