我需要编写一个方法,它接受一个整数数组并检查每个元素的所有除数(数字本身和 1 除外)是否都存在于该数组中。如果是,该方法将返回 true。
例如,下面的数组将返回 true:
4,5,10,2
我想不出可以实现的高效方法。你们能帮帮我吗?
我一直在考虑遍历数组中的每个元素,搜索它的所有除数,将它们放在数组中,返回数组,然后与原始数组中的元素进行比较。
这是一个可能的解决方案,它可以工作,但我想知道其他可能的解决方案。
编辑:这是我想出的代码,但速度非常慢。你们能帮我优化一下吗?:
import java.util.Arrays;
public class Divisors {
public static void main(String[] args) {
int[] numbers = { 4, 5, 10, 2 };
boolean flag = true;
for (int num : numbers) {
if (num % 2 != 0) {
for (int subNum = 1; subNum < num / 2; num += 2) {
if(num%subNum == 0 && subNum != 1) {
if(!Arrays.asList(numbers).contains(subNum)) {
flag = false;
}
}
}
} else {
for (int subNum = 1; subNum < num / 2; num++) {
if(num%subNum == 0 && subNum != 1) {
if(!Arrays.asList(numbers).contains(subNum)) {
flag = false;
}
}
}
}
}
System.out.println("Result is: "+flag);
}
}
最佳答案
我认为以下算法可以解决您的需求。我已经在几个案例中对其进行了测试,它似乎有效。 例如数组:
int[] set = {2, 3, 4, 5, 7, 10, 11, 15, 18, 35};
立即执行给出答案“真”。尝试删除答案为“false”的 7。
你这样调用它:
reduce(set, 0, 0)
使用的原理是递归迭代数组,通过每个元素分解数组来减少数组。如果你发现一个元素小于最后一个因子,这意味着它不能被分解。这仅在数组已排序时有效。一旦到达数组末尾,您就知道所有元素都已分解。
private static boolean reduce (int[] set, int index, int factor) {
// NOTE: set must be a sorted set of integers
if (index == set.length) {
return true;
} else {
int divisor = set[index];
if (divisor != 1) {
if (divisor < factor) return false;
for (int i = index; i < set.length; i++) {
while ((set[i]%divisor) == 0) {
set[i] = set[i]/divisor;
}
}
return reduce(set, index+1, divisor);
} else {
return reduce(set, index+1, factor);
}
}
}
看看它是否有效,如果您遇到任何问题,请告诉我。
关于java - 数组内的除数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27323303/