LintCode 4. 丑数 II

原题

解

第一步，万年不变的查错。如果给的n是小于1，那么这个就没什么意义了，return 0。

    public int nthUglyNumber(int n) {
        if (n < 1) {
            return 0;
        }
        ...
    }

这道题，找只含有质因数2，3，5的数。大体的做法就是从1开始，乘以2，3，5，找出最小的，再乘以2，3，5，和之前的比，找最小的。大致的code就是

public class Solution {
    /*
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        if (n < 1) {
            return 0;
        }
        List<Long> uglyNumbers = new ArrayList<>();
        uglyNumbers.add(1L);
        
        int twos = 0;
        int threes = 0;
        int fives = 0;

        for (int i = 1; i < n; i++) {
            Long last = uglyNumbers.get(uglyNumbers.size() - 1);
            while (uglyNumbers.get(twos) * 2 <= last) {
                twos++;
            }

            while (uglyNumbers.get(threes) * 3 <= last) {
                threes++;
            }

            while (uglyNumbers.get(fives) * 5 <= last) {
                fives++;
            }

            Long next = Math.min(uglyNumbers.get(twos) * 2, Math.min(uglyNumbers.get(threes) * 3, uglyNumbers.get(fives) * 5));
            uglyNumbers.add(next);
        }

        return uglyNumbers.get(uglyNumbers.size() - 1).intValue();
    }
}

解2

第一种方法比较没意思。我们可以想一下，从1开始，每一个数字都要乘以2，3，5，然后我们只去当前最小的，剩下的要跟以后乘出来的数字再排序，所以有木有一种data structure能即保留住这些乘出来又没有立即用到的数，又在我们需要的时候，很快的给我们下一个，即最小的数呢？MinHeap，or PriorityQueue。

public class Solution {
    /*
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        if (n < 1) {
            return 0;
        }
        
        Queue<Long> pq = new PriorityQueue<>();
        pq.add(1L);
        Set<Long> hash = new HashSet<>();
        int[] factors = new int[]{2, 3, 5};

        long num = 0;
        for (int i = 0; i < n; i++) {
            num = pq.poll();
            for (int j = 0; j < 3; j++) {
                long newNum = num * factors[j];
                if (!hash.contains(newNum)) {
                    pq.add(newNum);
                    hash.add(newNum);
                }
            }
        }

        return (int) num;
    }
}

code不难，就是需要一个HashSet来快速去重。

分析

时间复杂度

第一个解法，循环n次，每次3次计算2次对比，while循环的可以忽略，因为总共加起来也就能循环n次。这样的话，应该是O(n)。第二个解法，循环n次，每次poll的时候，PriorityQueue里面大概有3n的数，所以是O(log3n)，3可以忽略，也就是O(logn)，后面还要加3次。总共就是O(nlogn)。

空间复杂度

第一个解法，需要一个O(n)的list来放从1到n的数字。第二个需要一个O(n)的queue加O(n)的HashSet。

两种方法我更喜欢第二种，code更简便。但是第一种更效率。