查找整数,该整数将C ++中数组的最大元素数相除
在这个问题中,我们得到了n个整数的数组arr[]。
我们的任务是 找到整数,该整数将数组中元素的最大数量相除。
问题描述: 我们需要找到一个数字p,该数字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<<"将数组的最大元素相除的数字是 "<<findmaxDivElement(arr, n); return 0; }输出结果
将数组的最大元素相除的数字是 2