0%

神奇的优先队列

起因

美团面试时面试官出了一道算法题

https://leetcode.com/problems/ugly-number-ii/

面试时没解决 :(

解决

丑数的特点:

  1. 每个丑数都是前面数 x (2 | 3 | 5)其中之一
  2. 丑数按照从小到大的顺序排序

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int nthUglyNumber(int input) {
if(input == 0 || input == 1) {
return input;
}
int[] arr = new int[input];
int t2 = 0, t3 = 0, t5 = 0;
arr[0] = 1;
for(int i = 1; i < input ; i ++) {
arr[i] = Integer.min(arr[t2] * 2,Integer.min(arr[t3] * 3,arr[t5] * 5));
if (arr[i] == arr[t2] * 2) t2 ++;
if (arr[i] == arr[t3] * 3) t3 ++;
if (arr[i] == arr[t5] * 5) t5 ++;
}
return arr[input - 1];
}

我们有三个丑数,1,2,3,那下一个是多少?根据定义,下一个数是 2*(1,2,3), 3*(1,2,3), 5*(1,2,3) 中最小的一个数,这里显然是2,但2早已经在集合里面了。

所以更确切的说,下一个丑数是 2*(1,2,3), 3*(1,2,3), 5*(1,2,3) 中最小的且不在集合中的数。

我们可以假设集合中最初只有1,那么下一个数是 2* 1,再下一个数是 2 * 2,3 * 1,5 * 1 中最小的一个。

于是我们维护三个pointer,pointer与质因数(2 | 3 | 5)相乘,得到了(2 | 3 | 5)中与质因数相乘最小的丑数。

最大堆-优先队列

解决这个问题可以使用Java提供的两种数据结构。

  1. PriorityQueue(优先队列)
  2. TreeSet

首先弄明白几个概念:

优先队列和TreeSet的关系

PriorityQueue 使用数组存储,按顺序排列,作为队列,你只能获得他的最大,最小值,可以存储重复的值。

TreeSet可以保证数据全部按照某个顺序排列,不允许重复,可获得其中的任意值,提供比优先队列更多的特性,但同样意味着需要进行更多的计算。

优先队列和堆的关系

优先队列是一种抽象概念,描述了接口和它的行为,并不关联底层的具体实现

堆是一种数据结构,它可以通过某种方式来使得数据的存取高效。

巧合是的,优先队列使用堆这个数据结构来实现优先队列本身的抽象特点。

设计步骤

我们需要将计算出来的丑数存放到数组中,数组元素必须按照升序排列,最后的元素就是小于n的最大的丑数。

我们先用优先队列来解决这个问题

优先队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int nthUglyNumV2(int input) {
// Obviously, input must great than or equals to zero
if (input <= 1) {
return input;
}

PriorityQueue<Long> queue = new PriorityQueue<>();
queue.offer(1L);
for ( int i = 1 ; i < input ; i ++) {
Long num = queue.poll();
// 如果最小的数有重复,那么就去重
while(!queue.isEmpty() && queue.peek().equals(num)) num = queue.poll();
queue.offer(num * 2);
queue.offer(num * 3);
queue.offer(num * 5);
}
return queue.poll().intValue();
}

Java的优先队列默认使用最小堆,也即,poll 获得的是最小的值

每一次 for 都会将最小的值放在堆顶,从 1 开始,只需要再循环 n - 1 次,最后 poll 拉去的就是第 n 个丑数

由于使用队列时,数字会有重复,我们可以采用TreeSet来解决。

TreeSet

TreeSet,顾名思义,首先是 Set,意味着自动去重。

而根据 docs

1
The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

这里 TreeSet 会将整数按照升序排列

那我们的代码和上面的优先队列其实很相似,只不过不需要手动 while 去重了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int nthUglyNumV3(int input) {
// obviously, input must great than zero
if (input <= 1) {
return input;
}

TreeSet<Long> set = new TreeSet();
set.add(1L);
for(int i = 1 ; i < input; i ++){
Long num = set.pollFirst();
set.add(num * 2);
set.add(num * 3);
set.add(num * 5);
}
return set.pollFirst().intValue();
}

感想

每一道算法题都是独特的,最关键的是寻找出这道题的特点。

算法题往往涉及到某个数据结构,利用其特点对结果进行处理。

之前挺不喜欢刷题的,但最近看了好多算法,虽然平常几倍的性能差距没那么直观,但当量级逐渐上升之后,算法高效的优势就会显露无疑

这里侧重于解决算法问题,而不会手动实现数据结构,后面我会另起一篇文章来手写一个heap。