丑数求解以及丑数的优化

阳光穿透心脏的1/2处 2022-06-09 09:55 233阅读 0赞

#### 丑数： ####

**丑数是指因子只有2，3，5的数**  
**比如 6 因子2，3**  
**比如 15 因子3，5**  
**另外特别的，规定1为丑数**  
求第K个丑数？

最近在刷剑指offer的OJ时，在查找丑数的时候出现了超时的情况，特别记录下来优化的找法。

##### 第一种解法： #####

循环数字，为丑数时index+1，直到index==k

public static void find(int index){
            ArrayList<Integer> list = new ArrayList<Integer>(index);
            int i=1;
            while(list.size()!=index){
                if(judgeUglySum(i))
                      list.add(i);
                i++;
            }
            System.out.println(list.get(list.size()-1));
        }
        /*** * 消去所有丑数因子 * @param i 判断i是否是丑数 * @return */
        private static boolean judgeUglySum(int i) {
            while(i%2==0){
                //i/=2;
                i=i>>1; //除2 可以改为右移2
            }
            while(i%3==0){
                i/=3;
            }
            while(i%5==0){
                i/=5;
            }
            if(i==1){
                return true;
            }
            return false;
        }

这种的解法的缺点在于每次所有的数进行遍历（其中丑数只占一部分），在遍历更大都数字时会出现查找十分费时。仅仅index==1500，数字达到了8亿左右，耗时8秒；

##### 从丑数中找丑数 #####

下一步便是想办法从因子中找到最小的丑数  
我的思维：想从因子得乘积判断最小值判断 ，发现  
所以关键在于2，3，5乘什么；

1
          1*2=2
          1*3=3
          1*5=5
          2*2=4
          2*2*2=8
          3*2  =6

解决办法是用index2，index3，index5记录上次乘的下标；

public static void find2(int index){
            if(index<0){
                return -1;
            }
            if(index<7){  // 1-6 都是丑数
                return index;
            }
            int[] array = new int[index];
            array[0]=1;
            //用于记录2,3,5乘到哪一位了
            int index2 = 0,index3 = 0,index5 = 0;
    
            for(int i=1;i<index;i++){
                int tmp=array[index3]*3<array[index5]*5?array[index3]*3:array[index5]*5;
                array[i]=array[index2]*2<tmp?array[index2]*2:tmp;
                if(array[i]==array[index2]*2) index2++;  //表明这次是选的2 
                if(array[i]==array[index3]*3) index3++;
                if(array[i]==array[index5]*5) index5++;
            }
            System.out.println(array[index-1]);
            //return array[index-1];
        }

改良之后算第1500个丑数的时候，零毫秒。  
ps:但是会出现数字超出int范围的情况，在K=1692时丑数的时候就超出了整数的范围。  
算出从1到K=1692时，总共才费时34ms，和原来的8s相比天壤之别；  
这优化简直了，真的很佩服！  
总结：  
经过这次的练习让我觉得小的事情上还有如此多的玄机，连找个丑数这种看似很简单的问题，我最开始也没找到思路，最开始我就想在因子里面找，但是没想出来到底乘那个数字，因为最开始2最小，一直乘2也会变大。  
后来开始看第一种解法，循环求余，除去因子，最后判断结果是否为1。  
第二种解法，还是很巧妙的。