丑数Ⅰ

丑数Ⅱ

原题链接:
https://leetcode.cn/problems/ugly-number-ii/

解法1 优先队列

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
36
37
38
39

/**
 打表
 对于任意一个丑数 x，其与任意的质因数 (2、3、5)相乘，结果 (2x、3x、5x) 仍为丑数
 */
class Solution {
    public static final int N = 1690;
    public static int [] ans = new int[N];
    public static long [] nums = new long[]{2,3,5};

    static {
        // 最小堆
        // 这个点非常的坑 
        // Long 这里排序 不能用 o1 - o2 因为会存在溢出问题 一定要统一使用 o1.compareTo(o2)
        PriorityQueue<Long>pq = new PriorityQueue<>((o1, o2) -> o1.compareTo(o2));
        // 存储出现过的元素 防止再次入堆
        HashSet<Long> hash = new HashSet<>();
        pq.offer(1L);
        hash.add(1L);

        for(int i = 0 ; i < N ; i++){
            var x = pq.poll();
            ans[i] = x.intValue();
            for(var num : nums){
                long t = num * x;
                if(!hash.contains(t)){
                    pq.offer(t);
                    hash.add(t);
                }
            }
        }
    }

    public int nthUglyNumber(int n) {
        return ans[n - 1];
    }
}


解法2: 三指针

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
class Solution {
    public static int [] ans = new int[1690 + 1];

    static {
        ans[1] = 1;
        for(int i2 = 1,i3 = 1,i5 = 1,idx = 2  ; idx <= 1690 ;idx++){
            int a = ans[i2] * 2;
            int b = ans[i3] * 3;
            int c = ans[i5] * 5;

            int min = Math.min(a,Math.min(b,c));
            ans[idx] = min;

            // 2 质因子 已经可以作为小数 进行相乘 该为就可以跳过 不需要再相乘
            if(a == min){
                i2++;
            }

            if(b == min){
                i3++;
            }

            if(c == min){
                i5++;
            }

        }
    }

    public int nthUglyNumber(int n) {
        return ans[n];
    }
}