稳中向好
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。