LeetCode——264. 丑数 II(Java)

问题描述

题干:
给你一个整数 n ,请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 或 5 的正整数。

示例1:
输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例2:
输入:n = 1
输出:1
解释:1 通常被视为丑数。

题解分析

输出第n个丑数,首先我们要知道丑数的定义,定义就是题干说的那样,我们一般把1当作第一个丑数,依次往后排

当然思路很清晰就是生成丑数数组,最后返回第n个即可,但是怎么生成丑数的顺序数组呢

这里采用了Queue的一个实现类PriorityQueue,也就是一个最小堆模型,这样保证每次得到最小的元素

我们发现丑数肯定是2,3或者5的倍数,所以我们只要按照这个规律插入元素然后用PriorityQueue返回第n个即可

正确代码

 public int nthUglyNumber(int n){
        int[] factors = {2,3,5};
        PriorityQueue<Long> heap = new PriorityQueue<>();
        Set<Long> set = new HashSet();
        set.add(1L);
        heap.offer(1L);

        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int)curr;
            //添加2、3或者5的倍数
            for (int factor : factors) {
                long next = curr * factor;
                //排除重复元素
                if (set.add(next)){
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }

总结

这里使用了一个PriorityQueue实现类,这个类是模仿了最小堆的结构,保证了每次返回的元素都是堆中的最小值

如果用数组保存的话虽然可以查看其它元素,但是当然也会添加额外的空间消耗,当然官网也有动态规划方法,效率也是比这个高的

当然每次这种题目,总会有大佬采用面向结果编程,直接把答案数组返回,这肯定是不能超越的速度

如果文章存在问题或者有更好的题解,欢迎在评论区斧正和评论,各自努力,你我最高处见
上一篇:性能监控之常见 Java Heap Dump 方法


下一篇:堆排序思想及代码实现