数据结构
网络
关系数据库管理系统 (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 次浏览
广告