数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学在 C++ 中找到具有最大 GCD 的数组对
假设我们有一个正整数数组。我们的任务是从数组中找出整数对，其中 GCD 值最大。令 A = {1, 2, 3, 4, 5}，那么输出为 2。对 (2, 4) 的 GCD 为 2，其他 GCD 值都小于 2。
为了解决这个问题，我们将维护一个计数数组来存储每个元素的除数计数。计数除数的过程将花费大约 O(sqrt(arr[i])) 的时间。整个遍历结束之后，我们从最后一位索引遍历计数数组到第一位索引，然后如果我们发现某个值大于 1，那么这意味着它作为两个元素的除数以及最大 GCD。
示例
#include <iostream>
#include <cmath>
using namespace std;
int getMaxGCD(int arr[], int n) {
int high = 0;
for (int i = 0; i < n; i++)
high = max(high, arr[i]);
int divisors[high + 1] = { 0 }; //array to store all gcd values
for (int i = 0; i < n; i++) {
for (int j = 1; j <= sqrt(arr[i]); j++) {
if (arr[i] % j == 0) {
divisors[j]++;
if (j != arr[i] / j)
divisors[arr[i] / j]++;
}
}
}
for (int i = high; i >= 1; i--)
if (divisors[i] > 1)
return i;
}
int main() {
int arr[] = { 1, 2, 4, 8, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max GCD: " << getMaxGCD(arr,n);
}输出
Max GCD: 4
更新日期：2019 年 10 月 21 日
562 次浏览
广告