力扣： 49 丑数

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

  • 示例 1:
1
2
3
makefile复制代码输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
  • 提示
1
2
复制代码1 是丑数。
n 不超过1690。

解析

根据题意，我们可以有下面这种解法：丑数就是质因数只包含 2, 3, 5 的正整数。1是丑数

1.核心就是这句话：保证每个位置的丑数都有生成2、3、5的机会，且不漏过一个值！

2.循环结束后，保证每个位置的丑数都完成了2，3，5这三个操作！只不过重复值不会重复统计

3.确保每个丑数都会完成2，3，5这三个操作，如：b指向的丑数完成了一次3操作，就b++；

4.如果出现这种情况：dp[a] * 2 == dp[b] * 3,那么a和b都会完成自增，表示dp[a]这个丑数完成了2操作，dp[b]这个丑数完成了3操作，所以，下一个需要完成2操作的丑数是dp[a+1]，下一个需要完成3操作的丑数是dp[b+1]

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ini复制代码class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n]; //初始化存储丑数的数组
        dp[0] = 1;
        int a=0,b=0,c=0;
        
        for(int i=1;i<n;i++){
        dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
        if(dp[i] == dp[a]*2) a++; 
        if(dp[i] == dp[b]*3) b++;
        if(dp[i] == dp[c]*5) c++;
        }
        return dp[n-1];
    }
   
}

运行结果：

执行结果：通过

执行用时：2 ms, 在所有 Java 提交中击败了99.62%的用户

内存消耗：37.4 MB, 在所有 Java 提交中击败了73.38%的用户

此外还有最小堆算法：

要得到从小到大的第 nn 个丑数，可以使用最小堆实现。初始时堆为空。首先将最小的丑数 11 加入堆。每次取出堆顶元素 xx，则 xx 是堆中最小的丑数，由于 2x, 3x, 5x2x,3x,5x 也是丑数，因此将 2x, 3x, 5x2x,3x,5x 加入堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ini复制代码class Solution {
    public int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%