JZ33 丑数

自定义优先队列 比较器

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
//自定义优先队列 比较器
        PriorityQueue<int[]> que=new PriorityQueue<int[]>(
            new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {                
                return o1[0]-o2[0];
            }
        });
//第一个代表数字 第二个代表该数字的最小质因子， 1作为初始化 需要执行2,3,5所以1的质因子需要比2,3,5都大。
//然后就是最小堆，每次选出最小的那个就是第n个丑数
//同时每次把该数字乘以2,3,5构造出的丑数放入最小堆
//原理就是 2*3 = 6 = 3*2 重复了 通过判断只能产生3*2 而 2的最小质因子为2 不能乘3 就避免了重复乘，
//只有质数能保证这样的性质
//如果不是质数 需要用set集合
        que.offer(new int[]{1,6});
        int[] nums = new int[2];
        for(int i=0;i<index;i++){
            nums = que.poll();
            que.offer(new int[]{nums[0]*2,2});
            if(nums[1]>2){
                que.offer(new int[]{nums[0]*3,3});
                if(nums[1]>3)
                    que.offer(new int[]{nums[0]*5,5});
            }
        }
        return nums[0];
    }

}