Java large 性能

Question

我必须找到第 1000 个数字(不包括数字 3、4、7)，但这需要很长时间，大约 9 秒才能找出如何提高性能。

import java.sql.Date;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;

public class FirstChallange {

    private static int removedNumbers;
    private static int numberQuantity;
    private static int lastNumberFound; 
    private static int cont;
    private static int pos3;
    private static int pos4;
    private static int pos7;    

    public static void main(String[] args) 
    { 

        long inicio = System.currentTimeMillis();  

        removedNumbers = 0;
        numberQuantity = 10000000;


        for (cont = 1; removedNumbers <= numberQuantity; cont++) {      
            String str = new String(); 
            str = String.valueOf(cont);     

            pos3 = str.indexOf("3");
            pos4 = str.indexOf("4");
            pos7 = str.indexOf("7");

            if((pos3 == -1) && (pos4 == -1) && (pos7 == -1)) {
                removedNumbers++; 
                if(removedNumbers == numberQuantity){ // can not find numbers (3, 4, 7)
                    lastNumberFound = cont; 
                }
            } 
        }       

        DecimalFormat dfmt = new DecimalFormat("0");

        System.out.println(dfmt.format(lastNumberFound)); 

        long fim  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));  


    }
}

将数字转换为字符串并使用 indexOf 删除它们是最佳模式吗？或者有什么比像 RabinKarp 这样的 indexOf 更好的吗？

预期结果:5/4 秒后为 180999565

Answer 1

你应该以不同的方式思考问题。

“生成 numberQuantity 以下不包含 3、4、7 的所有数字”

或者换句话说:“创建仅包含 0、1、2、5、6、8、9 作为数字的数字”。

这是 7 个不同的数字。

因此，一种方法是增加一个从 1 开始的计数器并将其转换为以 7 为基数的表示形式，您可以像这样映射每个数字:

0->0
1->1
2->2
3->5
4->6
5->8
6->9