丑数

1.题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

2.暴力枚举求解

 public int GetUglyNumber_Solution(int index) {
+
+        if(index<1) return 0;
+
+        if(index ==1) return 1;
+
+        int UglyNumCount =1;
+        int count =1;
+
+        while (UglyNumCount <index){
+            count++;
+            if(isUglyNum(count)){
+                UglyNumCount++;
+               // System.out.println(String.format("第 %s 个丑数 %s",UglyNumCount,count));
+            }
+        }
+        return count;
+    }
+
+
+
+    // 判断一个数是否为丑数
+    public boolean  isUglyNum(int num){
+
+        while (num!=1){
+            if(num%2!=0 &&num%3!=0 && num%5!=0 )  break;
+
+            if(num%2==0)  num = num/2; // 对2整除
+            if(num%3==0)  num = num/3;  // 对3整除
+            if(num%5==0)  num = num/5;  // 对5整除
+        }
+
+        return num ==1;
+    }

3. 优化解法

    public int GetUglyNumber_Solution(int index) {

        if(index<1) return 0;
        if(index==1) return 1;

        Queue<Integer>  queue2  = new LinkedList<>();  // 2质数因子序列
        Queue<Integer>   queue3  = new LinkedList<>();  // 3质数因子序列
        Queue<Integer>   queue5  = new LinkedList<>();   // 5质数因子序列

        int count = 1;
        int current =1;   // 丑数种子

        while (count<index){
            // 种子生成新的丑数
            queue2.add(current*2);
            queue3.add(current*3);
            queue5.add(current*5);

            // 只需要比较 三个序列中最小的值即可，而最小的值就是最先放进去的值
            current = Math.min(Math.min(queue2.peek(),queue3.peek()),queue5.peek());
            if(queue2.peek() == current ) queue2.poll();
            if(queue3.peek() == current ) queue3.poll();
            if(queue5.peek() == current ) queue5.poll();
            count++;
        }
        return current;
    }