資料結構
網路
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 次瀏覽
廣告