大多數運行時間比較兩個非常大的數字（大於長）的有效方法

我想比較兩個非常大的數字。大多數運行時間比較兩個非常大的數字（大於長）的有效方法

我目前的方法有效，但在某些輸入上需要的時間超過2000毫秒。

我的代碼：

import java.io.*; 
import java.math.*; 
import static java.lang.Math.pow; 

public class comparelarge { 
    public static void main(String[] args) throws IOException { 
     InputStreamReader isr = new InputStreamReader(System.in); 
     BufferedReader bf = new BufferedReader(isr); 
     PrintWriter out = new PrintWriter(System.out); 

     String first = bf.readLine(); 
     String second = bf.readLine(); 
     BigInteger big1 = new BigInteger(first); 
     BigInteger big2 = new BigInteger(second); 

     if(big1.compareTo(big2) == 1){ 
      out.println('>'); 
      out.flush(); 
     } 
     else if(big1.compareTo(big2) == -1){ 
      out.println('<'); 
      out.flush(); 
     } 
     else{ 
      out.println('='); 
      out.flush(); 
     } 
    } 
}

請我如何能準確地比較大量的沒有過多的運行時間的建議。

來源

2017-05-13 Omar

1.）您正在執行compareTo兩次;將結果存儲在一個變量中並重用。（不要比較1/-1比較>0和<0

有一些東西在弦/優化直接，但你必須要小心，因爲這些可能會導致一些數字格式錯誤的答案。在我看來，這是最好的2）如果你只有正數而不是有0前綴的數字; 2）如果你只有正數而不是有前綴的數字，則使用0; 2）如果你只有正數，而不是有前綴的數字，則使用0。您可以在String.length上進行檢查，較長的字符串包含較大的數字。

3.）在相同長度的字符串上，您可以執行String.compareTo（），完全繞過BigInteger。

來源

2017-05-13 17:14:32

我編輯的代碼，當你在點1 提到和輸入可以包含0前綴在那一刻如此string.length減無益的compareTo使用1次，還是我得到的時間超過限制:( 任何更多的幫助將不勝感激謝謝。 – Omar

這些數字如何「大」是否準確？如果你有兩個字符串，你可以消除前導零，然後簡單地比較長度，或者如果他們是相同的，數字，從「頂部「。只要數字相同，轉到下一對，直到一個更高。這可能比轉換爲BigInteger更快。 –

當輸入超過50位數字時測試超出了時間限制，（沒有前導零） – Omar

大多數運行時間比較兩個非常大的數字（大於長）的有效方法

回答

相關問題