Ugly Number

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number.
The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Have you met this question in a real interview? Yes
Example
If K=4, return 9.

Challenge

O(K log K) or O(K) time.

Tags Expand

LintCode Copyright Priority Queue

思路

-参考来源

解法一：时间复杂度O(k log k)，空间复杂度O(k)

使用priority_queue模拟最小堆： 从中取出最小的 ugly number , 然后该 ugly number 分别乘以3, 5, 7 然后又放进 priority_queue中
如果上述过程中，将乘以3,5,7之后的数直接放入 priority_queue 将可能导致重复放入的问题，比如：当取出 9， 然后放入27, 45, 63,。后面当取出 21 时，放入 63, 105, 147，这里就重复放入 63 了。因此需要用个 hashset来 mark 哪些元素已经放入过了。
时间复杂度分析：共 k 个元素，每次取出一个元素时，都需要对堆进行操作，时间复杂度为 O(k)，因此时间复杂度为 O(k log k).

解法二：动规方法 时间复杂度 O(k)，空间复杂度O(k)

使用 primes 数组来记录前 k 个ugly_number。在生成 primes 数组时，新增入的元素，肯定是该 primes 数组中前面某些元素乘以3，或是乘以5，或是乘以7的结果，且是最小的。

丑陋数序列可以拆分为下面3个子列表：

(1) 3×3, 5×3, 7×3, 9×3, 15×3, …
(2) 3×5, 5×5, 7×5, 9×5, 15×5, …
(3) 3×7, 5×7, 7×7, 9×7, 15×7, …
我们可以发现每一个子列表都是丑陋数本身 乘以 3, 5, 7

接下来我们使用与归并排序相似的合并方法，从3个子列表中获取丑陋数。每一步我们从中选出最小的一个，然后向后移动一步。

class Solution {
    /**
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    public long kthPrimeNumber(int k) {
        // write your code here
        if (k <= 0) {
            return -1;
        }

        long[] uglyNumbers = new long[k + 1];
        int indexFor3 = 0, indexFor5 = 0, indexFor7 = 0; //multiplier index
        uglyNumbers[0] = 1;

        for (int i = 1; i <= k; i++) {
            uglyNumbers[i] = Math.min(Math.min(3 * uglyNumbers[indexFor3], 5 * uglyNumbers[indexFor5]), 7 * uglyNumbers[indexFor7]);
            if (uglyNumbers[i] == 3 * uglyNumbers[indexFor3]) {
                indexFor3++;
            }
            if (uglyNumbers[i] == 5 * uglyNumbers[indexFor5]) {
                indexFor5++;
            }
            if (uglyNumbers[i] == 7 * uglyNumbers[indexFor7]) {
                indexFor7++;
            }
        }

        return uglyNumbers[k];
    }
}