java 找到给定元素数组的 GCD
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/28391752/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the GCD for given array of elements
提问by vinod bazari
I had faced a interview question to find the gdc(greatest common divisor) for an integer array of element in optimised way :
我遇到了一个面试问题，以优化方式为元素的整数数组找到 gdc（最大公约数）：
Sample case :
a[] = { 10,20,19,15,13}
Result = 1
sample case :
a[]={9,21,12,15,27}
Result : 3
I have submitted following result during the interview. But he asked to optimise the same. Solution which I proposesd:
我在面试中提交了以下结果。但他要求优化相同。我提出的解决方案：
package threeDpalm;
public class GCF
{
public static void main(String ag [])
{
int[] input = {10, 20, 3, 30, 90, 40};
boolean flag = true;
int min_araay = Integer.MAX_VALUE;
int count = 0;
while (flag)
{
for (int j : input)
{
if (j < min_araay && j != 0)
{
min_araay = j;
}
}
for (int k = 0; k < input.length; k++)
{
input[k] = input[k]%min_araay;
if (input[k] == 0)
{
count++;
if (count == input.length)
{
flag = false;
System.out.println(min_araay);
break;
}
}
}
}
}
}
Can some one please help me with better solution
有人可以帮我找到更好的解决方案吗
回答by Lrrr
The easiest and the best way of computing GCD of a set is to compute GCDs one by one:
计算一个集合的 GCD 的最简单和最好的方法是一个一个地计算 GCD：
GCD(a1,a2, ... ,an) = GCD(GCD(a1,a2),a3, ... ,an)
GCD(a 1,a 2, ... ,a n) = GCD(GCD(a 1,a 2),a 3, ... ,a n)
So you could do it like this :
所以你可以这样做：
private int gcdFunc(int a, int b){
//TODO write this code.
}
public static void main(String args[])
{
int gcd = a[0];
for(int i = 1; i < n; i++)
gcd = gcdFunc(gcd, a[i]);
}
although your solution looks like a better solution but while loop looks very scary.
虽然您的解决方案看起来是更好的解决方案，但 while 循环看起来非常可怕。
