查找整数,该整数将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