对Leetcode 264题的一些思考

引言

• 本文展示了我对于leetcode264题的思考，如有不正确之处，请各位大神多多指教。

题目

• Write a program to find the n-th ugly number.
• Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
• Note that 1 is typically treated as an ugly number.

解法

• 思路：下一个丑数是上一个丑数乘以一个数（2 3 5），但是，这样算出来的丑数不一定是有序的，比如，上一个丑数是3，3*2=6也是丑数，但是比他小的4 5也是丑数，就被隔过去了。
• 所以如果能将上面的思路改写成一个有序的方法就好了。
• 在丑数的序列中，总能找到这样一个数，它乘2刚刚大于目前序列中最大的丑数，也总能找到这样一个数，它乘3刚刚大于目前序列中最大的丑数，也总能找到这样一个数，它乘4刚刚大于目前序列中最大的丑数，我们要找的“下一个丑数”即为上面三个数中最大的一个。
• 程序中，我们用m2、m3、m5三个下标，表示上述三个数在已经有序的丑数序列中的位置。
• 之所以每一循环，三个if均需检测，是因为如果遇到了某个丑数能够有多种方法分解（2 3 5）质因数，那么此时，m2、m3、m5三个下标可能需要同时移动，否则他们乘2（3或5）后就不是刚刚好大于目前序列中最大的丑数了。

程序

public class Solution {

    public int nthUglyNumber(int n) {
        if(n==1){
            return 1;
        }
        
        int m2 = 0;
        int m3 = 0;
        int m5 = 0;
        int tmp = 0;
        int count = 1;
        
        int[] uglyNumber = new int[n];
        uglyNumber[0]=1;
        
        while(count<n){
            tmp = Math.min(uglyNumber[m2]*2,Math.min(uglyNumber[m3]*3,uglyNumber[m5]*5));
            if(tmp==uglyNumber[m2]*2) m2++;
            if(tmp==uglyNumber[m3]*3) m3++;
            if(tmp==uglyNumber[m5]*5) m5++;
            uglyNumber[count] = tmp;
            count++;
        }
        
        return uglyNumber[n-1];
    }
}