LeetCode ugly Number II

264. Ugly Number II

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, and n does not exceed 1690.

方法

由于丑数都可被2或3或5整除,所以可以使用3个变量分别存放大于当前result[i]的是2,3,5的倍数的数,然后可得:result[i] = Math.min(t2,Math.min(t3,t5)),同时分别给t2,t3,t5三个指针,指出其大于result[i]的最小位置,然后根据最小位置的数求的新的t2,t3,t5.

public class Solution {
    public int nthUglyNumber(int n) {
        int[] result = new int[n];
        int c2 = 0;
        int c3 = 0;
        int c5 = 0;
        int t2 = 2;
        int t3 = 3;
        int t5 = 5;
        result[0] = 1;
        for(int i = 1; i < n; i++){
            result[i] = Math.min(t2,Math.min(t3,t5));
            while(t2 <= result[i]){
                t2 = result[++c2] * 2;
            }
            while(t3 <= result[i]){
                t3 = result[++c3] * 3;
            }
            while(t5 <= result[i]){
                t5 = result[++c5]* 5;
            }
        }
        return result[n-1];
    }
}
Share