leetcode-313-Super-Ugly-Number

发表于   |  

描述

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Example:

1
2
3
Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12, super ugly numbers given primes = [2,7,13,19] of size 4.

Note:

  • 1 is a super ugly number for any given primes.
  • The given numbers in primes are in ascending order.
  • 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
  • The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

分析

和 264. Ugly Number II 一样，不过这里需要根据质数集合的大小来指定子序列的数量，可以用一个数组来存储子序列的索引，比如 indexes[i] 就表示第 i 个子序列的索引。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] indexes = new int[primes.length];
        List<Integer> result = new ArrayList<Integer>();
        
        result.add(1);
        while(result.size() < n) {
            int minValue = Integer.MAX_VALUE;
            
            for (int i = 0; i < primes.length; i++) {
                minValue = Math.min(minValue, result.get(indexes[i]) * primes[i]);
            }
            result.add(minValue);
            for (int i = 0; i < primes.length; i++) {
                if (minValue == primes[i] * result.get(indexes[i])) {
                    indexes[i]++;
                }
            }
        }
        return result.get(result.size()-1);
    }
}

相关问题

(M) Ugly Number II

题目来源