找到給定整數的最小Antiprime的更好算法

-2

我在HackerRank上找到了這個問題，我們應該在這裏找到最小的AntiPrime數（正整數是antiprime當且僅當它有更多的除數比任何其他正整數小比本身）。找到給定整數的最小Antiprime的更好算法

因此，如果用戶輸入5，則最小antiprime數目將是6，如圖6具有比任何數目的約數的B/W爲1〜5

我的方法： - 存儲除數對於每個數編號1到n在一個散列集中，然後從n + 1檢查具有比HashSet中的更多除數的整數。

public static int send(int n) 
    { 
     HashSet hs = new HashSet() ; 
     for(int i=1 ; i<=n ; i++) 
     { 
      hs.add(div(i)) ; 
     }  
     for(int i= n+1 ; ; i++) 
     { 
      if(Collections.max(hs).compareTo(div(i)) < 0) 
      { 
       return i ; 
      }  
     }  
    }  
    public static int div(int n) 
    { 
     int ctr = 0 ; 
     for(int i=1 ; i<=n ; i++) 
     { 
      if(n % i == 0) 
       ctr++ ; 
     }  
     return ctr ; 
    }

該邏輯工作完美，但在所有的測試用例中它返回超時，因爲我看到它的複雜性是O（n^2）。

所以，請給我一個更好的算法，這個算法可以在相對較短的時間內完成。

來源

2016-07-27 Ashutosh Agarwal

對於人們downvoting問題，請註明原因。我覺得這很無禮。 –

歡迎來到堆棧溢出... – kpie

您的循環div應該只能達到n的sqrt。 – kpie

您可以使用一個Set<>數據結構，然後您可以在每次除數達到峯值（Antiprime數字）時存儲。然後，您可以撥打ceiling()之類的號碼以獲得號碼中的下一個最大號碼，因此對於5，它將在O(logn)時間內返回6。另外，對於輸出，使用StringBuilder並生成結果並輸出。對我而言，它起初不起作用，System.out.println()，但StringBuilder，然後append()的結果。最後，在StringBuilder上做.toString()。作爲參考，我在比賽中排名第8（2000+以上），所以它對我有效，然後變得完美。

來源

2016-07-27 17:38:51 MathBunny

納入我在這裏的評論中提到的修改：

public static int send(int n) 
    { 
     HashSet hs = new HashSet() ; 
     for(int i=int(n/2)+1 ; i<=n ; i++) 
     { 
      hs.add(div(i)) ; 
     } 
     int markToBeat = Collections.max(hs); 
     for(int i=n+1 ; ; i++) 
     { 
      if(div(i) > markToBeat) 
      { 
       return i ; 
      } 
     }  
    }  
    public static int div(int n) 
    { 
     int ctr = 0 ; 
     for(int i=1 ; i<=sqrt(n) ; i++) 
     { 
      if(n % i == 0) 
       ctr++ ; 
     }  
     return ctr ; 
    }

來源

2016-07-27 17:41:39 kpie

找到給定整數的最小Antiprime的更好算法

回答

相關問題