Sorted排列的时间限制与重复排名

Question

首先我想提一下，我不是很擅长编程。我试图解决重复排列问题，但我不明白为什么我总是得到时间限制。我的代码是在java中，我使用BigInteger进行阶乘和其他计算。

请帮我找出是什么原因，我有时间限制。我发现了同样的方法来解决这个问题，但这是在Python中。在这里我提供了我的代码。提前致谢。

import java.math.BigInteger; 
public class Solution { 
    BigInteger factorial(int n){ 
     BigInteger sum=new BigInteger(String.valueOf(1)); 

     if(n<2) return new BigInteger(String.valueOf(n)); 
     for(int j=2;j<=n;j++){ 
      sum=sum.multiply(new BigInteger(String.valueOf(j))); 

     } 
     return sum; 
    } 
    public int findRank(String a) { 
     if(a.length()<2) return 1; 
     Map<Character,Integer> map1=new HashMap<Character,Integer>(); 
     BigInteger sum=new BigInteger(String.valueOf(1)); 

     for(int i=0;i<a.length();i++){ 
      if(!map1.containsKey(a.charAt(i))){ 
       map1.put(a.charAt(i),1); 
      } 
      else{ 
       int cc=map1.get(a.charAt(i)); 
       cc=cc+1; 
       map1.put(a.charAt(i),cc); 
      } 
     } 
     BigInteger temp1=new BigInteger(String.valueOf(1)); 
     for (Map.Entry<Character, Integer> entry : map1.entrySet()) 
     { 

      temp1=temp1.multiply(new BigInteger(String.valueOf(factorial(entry.getValue())))); 

     } 
     temp1=temp1.pow(1000001); 
     temp1=temp1.mod(new BigInteger(String.valueOf(1000003))); 
     for(int i=0;i<a.length();i++){ 

       BigInteger rank=new BigInteger(String.valueOf(0)); 

       for(int j=i+1;j<a.length();j++){ 
        if(a.charAt(i)>a.charAt(j)){ 
         rank=rank.add(new BigInteger(String.valueOf(1))); 
        } 
       } 
       BigInteger temp=new BigInteger(String.valueOf(factorial(a.length()-i-1))); 

       rank=rank.multiply(temp1); 
       rank=rank.multiply(temp); 

       sum=sum.add(rank); 
       sum=sum.mod(new BigInteger(String.valueOf(1000003))); 
     } 
     return sum.intValue(); 
    } 
} 

Answer 1

您使用了过多的字符串解析和对象创建。这一切在运行时都很昂贵。

随着BigInteger的优化使用，该方法将在我的主站上返回约1ms。

public class Solution { 

     private BigInteger factorial(final int n) { 
      BigInteger sum = BigInteger.ONE; 

      if (n < 2) { 
       return BigInteger.valueOf(n); 
      } 

      for (int j = 2; j <= n; j++) { 
       sum = sum.multiply(BigInteger.valueOf(j)); 

      } 
      return sum; 
     } 

     public int findRank(final String a) { 

      if (a.length() < 2) { 
       return 1; 
      } 

      final Map<Character, Integer> map1 = new HashMap<>(); 
      BigInteger sum = BigInteger.ONE; 

      for (int i = 0; i < a.length(); i++) { 
       final char charAt = a.charAt(i); 

       if (!map1.containsKey(charAt)) { 
        map1.put(charAt, 1); 
       } else { 
        int cc = map1.get(charAt); 
        map1.put(charAt, cc++); 
       } 
      } 

      BigInteger temp1 = BigInteger.ONE; 

      for (final Map.Entry<Character, Integer> entry : map1.entrySet()) { 
       temp1 = temp1.multiply(factorial(entry.getValue())); 
      } 

      temp1 = temp1.pow(1000001); 
      temp1 = temp1.mod(BigInteger.valueOf(1000003)); 

      for (int i = 0; i < a.length(); i++) { 

       BigInteger rank = BigInteger.ZERO; 

       for (int j = i + 1; j < a.length(); j++) { 
        if (a.charAt(i) > a.charAt(j)) { 
         rank = rank.add(BigInteger.ONE); 
        } 
       } 

       final BigInteger temp = factorial(a.length() - i - 1); 

       rank = rank.multiply(temp1); 
       rank = rank.multiply(temp); 

       sum = sum.add(rank); 
       sum = sum.mod(BigInteger.valueOf(1000003)); 
      } 
      return sum.intValue(); 
     } 
    }