题目描述

设计一个算法，找出只含素因子2，3，5 的第 n 大的数。1也是一个丑数。

思路

• 方法一
  每个丑数都是2..3..5..的结果
  创建保存丑数的数组a，设a[0]=1
  用index2，index3，index5表示丑数分解包含了2、3、5的个数，初始化为0
  每次求min(a[indexk]k)，得到当前最小的丑数，写入数组，并将indexk++
  这样做即可保证a数组中能保存所有的按序排列的丑数，输出第a[n-1]个元素即可。

• 方法二
  将1加入保存丑数的数组a，将2,3,5加入优先队列pq
  每次从pq取min，如果min与a[tmp]不等，数组保存min，并将min*2,3,5的值加入优先队列。如果相等，跳过。
  这样做，最终可以得到a[n-1]个元素即为结果

代码

 int nthUglyNumber(int n) {
        // Write your code here
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;
        int[] res = new int[n];
        res[0] = 1;
        int count = 1;
        while(count < n){
            res[count] = min(res[index2]*2, res[index3]*3, res[index5]*5);
            if(res[count] == res[index2]*2) index2++;
            if(res[count] == res[index3]*3) index3++;
            if(res[count] == res[index5]*5) index5++;
            count++;
        }
        return res[--count];
    }
    private int min(int a1, int a2, int a3){
        if(a1 < a2){
            if(a1 < a3)
                return a1;
            else
                return a3;
        }else if(a2 < a3){
            return a2;
        }else{
            return a3;
        }
    }

考差点

• 优先队列
• 数组下标的灵活运用