Leetcode-0XX

Leecode-264-丑数

题目描述

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:

输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:

输入: 14
输出: false 
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：

1. 1 是丑数。
2. 输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。

方法一：除法

• 思路：不断除以2，3，5 ，最后结果是1，那么一定是丑数
  • 换句话来说：除尽所有的因子，那么最后一定等于1

class Solution {
    public boolean isUgly(int num) {
        
        if (num <= 0){
            return false;
        }
        
        
        while (num % 5 == 0){
            num /= 5;
        }
        
        while (num % 3 == 0){
            num /= 3;
        }
        
        while (num % 2 == 0){
            num /= 2;
        }
        
        
        return num == 1;
    }
}

复杂度分析：

• 时间复杂度： O(1)
• 空间复杂度： O(1)

题目描述（丑数进阶）：

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

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

方法一：三指针

思路：

• 创建一个大小是 n+1 的数组，来存放n个丑数（第一个丑数是numList[0] = 1）

• 存入的每个丑数是2，3，5对应指针最小的那个丑数

• 三个指针分别指向2,3,5的因子

  • 如果含有2的因子，2的指针加1
  • 如果含有3的因子，3的指针加1
  • 如果含有5的因子，5的指针加1

• 最后返回数组下标 n - 1对应的元素即可

方法二：最小堆

思路：

• 从堆中包含一个数字开始：1

• 去计算下一个丑数。将 1 从堆中弹出然后将三个数字添加到堆中：2，3，5

• 现在堆中最小的数字是 2。为了计算下一个丑数，要将 2 从堆中弹出然后添加三个数字：4，6，10

// 堆：队列实现

class Solution2 {
    public int nthUglyNumber(int n) {
        // 存放丑数
        int[] nums = new int[n + 1];
        // 用来对堆去重
        HashSet<Long> set = new HashSet<>();
        // 在每个步骤中，弹出堆中最小的丑数 k，并
        // 在堆中添加三个丑数：k×2, k×3，和 k×5
        PriorityQueue<Long> pq = new PriorityQueue<>();

        // 同时加入第一个丑数
        pq.add(1L);
        set.add(1L);

        // 初始化丑数和因子
        long currUgly = 1L;
        long newUgly  = 1L;
        int[] primes = new int[]{2,3,5};

        // 从堆中包含第一个数字开始
        // 重复该步骤计算所有丑数。
        for (int i = 0; i < n; i++) {
            // 弹出堆中最小的丑数 k
            currUgly = pq.poll();
            // 将这个丑数加入到数组存放
            nums[i] = (int)currUgly;
            // 添加三个新丑数
            for (int prime : primes) {
                newUgly = currUgly * prime;
                if (!set.contains(newUgly)){
                    set.add(newUgly);
                    pq.add(newUgly);
                }
            }
        }
        return nums[n - 1];
    }
}

• 时间复杂度：O(n) 对每个丑数乘以因子的for循环操作。
• 空间复杂度：O(n) 数组的长度，Set的长度

打赏