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.

Analysis

1. return if n<=0
2. new list (store ugly numbers), add 1 as the 1st element
3. int a,b,c=0
4. while (list.size<n):
   1. int next = min(list(a)x2, list(b)x3, list(c)x5)
   2. add next to list
   3. check which value is added, move corresponding index
5. return last element of list

Code

public class Solution {
    public int nthUglyNumber(int n) {
        if (n<=0) {return 0;}
        List<int> uglylist = new LinkedList<int>();
        int a=0, b=0, c=0;
        uglylist.add(1);
        while (uglylist.size()<n){
            int next = Math.min(uglylist.get(a)*2, Math.min(uglylist.get(b)*3, uglylist.get(c)*5));
            uglylist.add(next);
            if (next == uglylist.get(a)*2) {a++;}
            if (next == uglylist.get(b)*3) {b++;}
            if (next == uglylist.get(c)*5) {c++;}
        }
        return uglylist.get(uglylist.size()-1);
    }
}

Note

1. List, not List
2. 注意while里面一定都要用if，不能用else if。应为三个算出来的数有可能是重复的。如果重复的话，用if可以都check一遍，如果有两个或三个都是最小值，那么指针都要移动。

Reference

Leetcode