p313

发表于 | 分类于 |

LeetCode p313 Super Ugly Number 题解

1.题目：

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. For example, [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.

题意：

求第n小的最丑数，最丑数的定义为他的因子里面只有1和输入的数组中的数。

2.解题思路:

这道题我真的写了好久。。泪眼汪汪TUT
期间我还问了罗狗狗！！感谢他为我指点迷津！简直豁然开朗！虽然后面还是调了一堆bug.
解题思路是这样的，ans数组存取答案从小到大，所以第n小的就是ans[n-1]。
然后每次为其添加一个最小值。
注意以2 3 5 为例
1
1 2
1 2 3
1 2 3 4 （4=2*2)
1 2 3 4 5

要有一个p数组与primes数组相关联，记录它乘到ans数组的哪个位置了，避免重复计算。
。。思想就是这样的了，每次循环取小就行。。TUT然而我写了那么久。
最后再次感谢罗狗狗。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
       int[] ans = new int[n];
		int len = primes.length;
		int[] p = new int[len];
		
		if (n == 0 || primes == null)
			return 0;
		if (n == 1)
			return 1;
		ans[0] = 1;
		
		for (int i = 1; i < n; i++) {
			ans[i] = Integer.MAX_VALUE;
			for (int j = 0; j < len; j++) {
				//System.out.println(j + "  " + i + "  " + p[j]);
				ans[i] = Math.min(ans[i], ans[p[j]] * primes[j]);

			}
			for (int j = 0; j < len; j++) {
				if (ans[i] == ans[p[j]] * primes[j]) {
					
						p[j]++;
					
				}
			}
			//System.out.println(Arrays.toString(primes));
			//System.out.println(Arrays.toString(p));

		}
		return ans[n-1];
    }
}

4.一些总结：