【LeetCode】Ugly Number II解題報告

Ugly Number II
[LeetCode]
https://leetcode.com/problems/ugly-number-ii/
Total Accepted: 12227 Total Submissions: 54870 Difficulty: Medium
Question
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Examples
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.
Ways
方法1
最も簡単な方法は遍歴する方法で、直接各数が醜いかどうかを判断して、もしリストに入れるならば、これは方法の1です.
しかし、この方法は効率が低すぎて、提出時に3回連続して時間の制限を超えています.ローカルで実行してもいいです.仕方なく、効率を上げなければならない.
方法2
すべてのugly numberは1から始まり,2/3/5を乗じて生成される.
これらの生成数を並べ替えるだけで入手でき、自動並べ替えはsetを使用できます
このようにして取り出す最初の要素が最小要素であり、これにより新たなugly numberの生成が継続する.
次の3つのグループに分けることができます.
(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …
各グループが使用した数値を削除すると、リストに1つの要素しかなく、3つのグループの最小値を取得した後、次のブス数を計算します.

public static int nthUglyNumber2(int n) {
    List<Integer> num2List = new ArrayList<Integer>();
    List<Integer> num3List = new ArrayList<Integer>();
    List<Integer> num5List = new ArrayList<Integer>();

    num2List.add(1);
    num3List.add(1);
    num5List.add(1);

    int test = 0;

    for (int j = 0; j < n; j++) {
        //    
        test = Math.min(Math.min(num2List.get(0), num3List.get(0)), num5List.get(0));

        //            
        if (num2List.get(0) == test) num2List.remove(0);
        if (num3List.get(0) == test) num3List.remove(0);
        if (num5List.get(0) == test) num5List.remove(0);

        num2List.add(2 * test);
        num3List.add(3 * test);
        num5List.add(5 * test);
    }


    return test;
}

Solution
私のGitHubに預けられています.
https://github.com/fuxuemingzhu/UglyNumber2
Captures
テスト結果のスクリーンショット:
Reference
http://blog.csdn.net/guang09080908/article/details/47780619
http://blog.csdn.net/xudli/article/details/47903959
Date
2015/10/18 20:57:01