丑数问题及变种小结

声明

1 判断丑数

因子只包含2,3,5的数称为丑数(Ugly Number)，习惯上把1当作第一个丑数面试

lintcode 517 ugly numbersegmentfault

剑指offer 面试题34 丑数数组

解法：参考剑指offer，将待判断目标依次连续整除2，3，5，若是最后获得1，证实该数为丑数；优化

/**

* 依次整除2，3，5判断(2，3，5顺序判断时间最优)

* http://www.lintcode.com/zh-cn/problem/ugly-number/

* 题意：判断一个数是不是丑数

* @author yzwall

*/

class Solution {

public boolean isUgly(int num) {

if (num == 0) {

return false;

}

if (num == 1) {

return true;

}

while (num % 2 == 0) {

num /= 2;

}

while (num % 3 == 0) {

num /= 3;

}

while (num % 5 == 0) {

num /= 5;

}

return num == 1 ? true : false;

}

}

2 找出第k大丑数

lintcode 4 ugly number iies5

剑指offer 面试题34 丑数拓展.net

丑数推论

根据丑数定义，有推论以下：

任取一个丑数$m$，记$m2 = mtimes2$，$m3 = mtimes3$，$m5 = mtimes5$code

$m2$，$m3$和$m5$必然是丑数；blog

若是$m$为当前第$n$个丑数，那么$m2$, $m3$和$m5$中的最小值必然是第$n+1$个丑数；队列

2.1 解法1：$O(nlogn)$时间复杂度

经过丑数推论，用优先队列PriorityQueue的队首保存当前第$n$个丑数，用哈希表HashSet保证优先队列中没有重复丑数；

/**

* 题意：求第n个丑数

* http://www.lintcode.com/zh-cn/problem/ugly-number-ii/

* 解法1：优先队列+HashSet求解，时间复杂度O(nlogn)

* @author yzwall

*/

class Solution13 {

public int nthUglyNumber(int n) {

PriorityQueue pq = new PriorityQueue<>(n, new Comparator(){

public int compare(Long o1, Long o2) {

return o1 < o2 ? -1 : 1;

}

});

HashSet hash = new HashSet<>();

hash.add(1L);

pq.offer(1L);

int[] primes = new int[]{2, 3, 5};

for (int prime : primes) {

hash.add((long)prime);

pq.offer((long)prime);

}

long min = primes[0];

for (int i = 0; i < n; i++) {

// min始终为第i+1个丑数，优先队列提供保证

min = pq.poll();

for (int prime : primes) {

if (!hash.contains(min * prime)) {

hash.add(min * prime);

// HashSet保证优先队列中无重复丑数

pq.offer(min * prime);

}

}

}

return (int)min;

}

}

2.2 解法2：$O(n)$时间复杂度

根据丑数推论，与解法2.1相比，

对于当前第$n$个丑数$m$，找到超过$m$的第一个$m2$,$m3$和$m5$，三者之间的最小者必然是第$n+1$个丑数

用数组保存生成的丑数，避免使用优先队列和哈希表，时间复杂度优化到$O(n)$，空间复杂度仍然为$O(n)$

代码部分参考剑指offer 面试题34 丑数拓展

3 找出第k大自定义丑数

自定义丑数的定义是正整数而且全部的质数因子都在所给定的一个大小为 k 的质数集合内。

好比指定质数集合为 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前12个超级丑数

自定义丑数是广义化的丑数，丑数的质数集合指定为[2, 3, 5]

lintcode 518 siper ugly number

3.1 解法1：$O(nlog n)$时间复杂度

丑数推论，可推广至自定义丑数：

任取一个自定义丑数$m$，记指定质数集合为$primes[]$， 记${m}_{i} = mtimes primes[i], i = 0,1,2,...,primes.length - 1$

${m}_{i}$必然是自定义丑数；

若是$m$为当前第$n$个丑数，那么${m}_{i}$中的最小值必然是第$n+1$个自定义丑数；

经过上述推论，用优先队列PriorityQueue的队首保存当前第$n$个自定义丑数，用哈希表HashSet保证优先队列中没有重复自定义丑数；

/**

* 题意：求第n个自定义丑数

* http://www.lintcode.com/zh-cn/problem/super-ugly-number/

* 解法1：优先队列+HashSet求解，时间复杂度O(nlogn)，空间复杂度O(n)

* @author yzwall

*/

class Solution {

public int nthSuperUglyNumber(int n, int[] primes) {

PriorityQueue pq = new PriorityQueue<>(n, new Comparator(){

public int compare(Long o1, Long o2) {

return o1 < o2 ? -1 : 1;

}

});

HashSet hash = new HashSet<>();

hash.add(1L);

pq.offer(1L);

for (int prime : primes) {

hash.add((long)prime);

pq.offer((long)prime);

}

long min = primes[0];

for (int i = 0; i < n; i++) {

min = pq.poll();

for (int prime : primes) {

if (!hash.contains(min * prime)) {

hash.add(min * prime);

pq.offer(min * prime);

}

}

}

return (int)min;

}

}