阵列内的除数

我需要编写一个方法，该方法接受一个整数数组，并检查每个元素是否存在于此数组中的所有除数（数字本身和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); 
     } 
}

来源

2014-12-05 David Lasry

+10

“我想不出有效率的东西能实施，你们能帮我出去吗？”从效率低下开始，在代码审查上分享代码，他们会帮助你改进。如果你确实有尝试过的东西，但它不起作用，请在这里分享这些代码以及你遇到的错误。 – 2014-12-05 19:36:08

把所有的元素放在一个'TreeSet '中，找到每个元素的所有除数（可选地将它们放在'Set'中），检查是否存在。集合具有良好的查找/交集性能。 – 9000 2014-12-05 19:36:50

@ 9000这也需要太多时间= \ – 2014-12-05 19:39:57

我认为以下解决算法FFT您的需要。我已经在少数情况下进行了测试，似乎可行。例如，阵列：

int[] set = {2, 3, 4, 5, 7, 10, 11, 15, 18, 35};

立即执行回答“true”。尝试删除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); 
     } 

    } 
}

看看它是否有效，让我知道如果你遇到任何问题。

来源

2014-12-05 19:47:19 Svea

我很想知道这是否解决了您的问题？ – Svea 2014-12-09 06:23:20

1.遍历数组中的每个元素 2.在for循环中查找其除数 3.在执行2）时，检查每个除数是否包含在数组中。如果为false - 返回false。

来源

2014-12-05 21:45:27

我试着做你的建议，它的工作原理，但代码是超慢（它需要5秒来确定只有4个元素的数组的真或假）。我把它添加到帖子中。你可以看一下吗？ – 2014-12-06 05:15:58

阵列内的除数

回答

相关问题