資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢整除陣列中最多元素的整數
在這個問題中，我們給定一個包含 n 個整數的陣列 arr[]。
我們的任務是查詢整除陣列中最多元素的整數。
問題描述：我們需要找到一個數字 p，它可以整除陣列中的最多元素。如果有多個這樣的元素，我們將返回較小的那個。
讓我們來看一個例子來理解這個問題：
輸入：arr[] = {4, 5, 6, 7, 8}
輸出：2
解釋：
元素 2 整除 {4, 6, 8}。
解決方案
解決這個問題的一個簡單方法是遍歷陣列，然後對於陣列的每個元素，用 1 到 k 之間的元素除陣列中的每個元素。並返回整除陣列中最多元素的元素。
另一種方法是利用陣列的所有元素都可被質因數整除的事實。
我們將儲存每個質數的除法頻率，然後返回頻率最高的因子。我們將質數及其頻率儲存在一個雜湊表中。
程式演示了我們解決方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
int primes[MAXN];
void findPrimeSieve()
{
primes[1] = 1;
for (int i = 2; i < MAXN; i++)
primes[i] = i;
for (int i = 4; i < MAXN; i += 2)
primes[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (primes[i] == i) {
for (int j = i * i; j < MAXN; j += i)
if (primes[j] == j)
primes[j] = i;
}
}
}
vector<int> findFactors(int num)
{
vector<int> factors;
while (num != 1) {
int temp = primes[num];
factors.push_back(temp);
while (num % temp == 0)
num = num / temp;
}
return factors;
}
int findmaxDivElement(int arr[], int n) {
findPrimeSieve();
map<int, int> factorFreq;
for (int i = 0; i < n; ++i) {
vector<int> p = findFactors(arr[i]);
for (int i = 0; i < p.size(); i++)
factorFreq[p[i]]++;
}
int cnt = 0, ans = 1e+7;
for (auto itr : factorFreq) {
if (itr.second >= cnt) {
cnt = itr.second;
ans > itr.first ? ans = itr.first : ans = ans;
}
}
return ans;
}
int main() {
int arr[] = { 4, 5, 6, 7, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The number that divides the maximum elements of the array is "<<findmaxDivElement(arr, n);
return 0;
}輸出
The number that divides the maximum elements of the array is 2
更新於：2021年1月25日
321 次瀏覽
廣告