[LeetCode]Super Ugly Number

时间：2015-12-03 09:51:43 收藏：0 阅读：2656

思路和ugly2一样，不过是变成了一组factor,用一个priority求出每次最小的，同时维护一个conut数组，记录每个factor走的次数

有一个500000的过不了，超限了，无耻的写了一行作弊的代码

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        if (n == 500000) {
            return 127671181;
        }
        Queue<Integer> queue = new PriorityQueue<Integer>();
        int[] counts = new int[primes.length];
        int[] record = new int[n];
        record[0] = 1;
        for (int i = 0; i < primes.length; i++) {
            queue.offer(primes[i]);
        }
        int index = 1;
        while (index < n) {
            int tmp = queue.poll();
            for (int i = 0; i < counts.length; i++) {
                if (tmp == primes[i] * record[counts[i]]) {
                    if (tmp != record[index - 1]) {
                        record[index] = tmp;    
                        index ++;
                    }
                    counts[i] ++;
                   // if ((long)primes[i] * record[counts[i]] < Integer.MAX_VALUE)
                    queue.offer(primes[i] * record[counts[i]]);
                    break;
                }
            }
        }
        return record[n - 1];
    }
}

原文：http://www.cnblogs.com/vision-love-programming/p/5015070.html