超级丑数 Super Ugly Number

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Input: n = 12, primes = [2,7,13,19]
Output: 32

思路

查找第n个丑数，这个类型的问题，基本有2个思路：

1 使用队列和哈希表进行处理。

2 使用N指针处理。

第一种容易理解，在问题规模并不大的情况下，可以采用。
第二种方法，需要通过数学思考，通过处理避免去产生可能重复的数字。
第三种方法，DP，暂时不考虑。

当出现像一组的prime factor，方法一就会出现时间复杂度和空间复杂度会超出我们的容忍度。

在计算第n个丑数的时候，必须知道前n-1个丑数是多少，然后分别和prime factor相乘得到一组数，从中选择最小的一个。如果使用暴力计算，是可以得到每一个数字，但是问题是会出现重复的结果。

建立一个用于存放丑数结果的ArrayList命名list

此处我们借助指针数组，建立一个长度为primes.length的数组pos，pos[i]表示primes[i]下一步要去乘list中的第pos[i]个丑数。

通过循环计算出一轮选择Min(primes[i]*list.get(pos[i]))，准备放入list，如果任何一个primes[i]*list.get(pos[i])和ans相等，说明有重复，对应的pos[i]后移一位，用来保证每次乘积都是当前这个prime能乘出的最小值，并且不会重复。

public int nthSuperUglyNumber(int n, int[] primes){
	int[] pos = new int[primes.length];
	List<Integer> list = new ArrayList<>();
	list.add(1);
	int ans =1;
	while(list.size<n){
		ans = list.get(pos[0])*primes[0]; // ans must be seted in every loop
		for(int i =1;i<primes.length;i++){
			ans = Math.min(ans,list.get(pos[i])*primes[i]);
		}	
		
		for(int i =0;i<primes.length;i++){
			if(list.get(pos[i])*primes[i]==ans){
				pos[i]++;
			}
		}
		list.add(ans);
	}
	return ans ;
}

Tag

math