陣列內的除數

我需要編寫一個方法，該方法接受一個整數數組，並檢查每個元素是否存在於此數組中的所有除數（數字本身和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

陣列內的除數

回答

相關問題