剑指 Offer 49. 丑数

Offer_49

题目详情

解法一：小根堆+哈希表/HashSet

根据丑数的定义，如果a是丑数，那么a2, a3以及a*5都是丑数
可以使用小根堆存储按照从小到大排序的丑数。

package com.walegarrett.offer;

import java.util.HashMap;

import java.util.PriorityQueue;

/**

 * @Author WaleGarrett

 * @Date 2021/2/8 21:39

 */

/**

 * 题目详情：编写一个程序，找出第 n 个丑数。

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

 */

public class Offer_49 {

    public int nthUglyNumber(int n) {

        PriorityQueue<Long>queue = new PriorityQueue<>();

        HashMap<Long,Integer>map = new HashMap<>();

        queue.offer(1L);

        int cnt = 0;

        long now = 1;

        while(cnt < n){

            now = queue.poll();

            if(!map.containsKey(now*2)){

                queue.offer(now * 2);

                map.put(now*2, 1);

            }

            if(!map.containsKey(now*3)){

                queue.offer(now * 3);

                map.put(now*3, 1);

            }

            if(!map.containsKey(now*5)){

                queue.offer(now * 5);

                map.put(now*5, 1);

            }

            cnt++;

        }

        return (int)now;

    }

}

解法二：动态规划

/**

 * 解法二：动态规划

 */

class Offer_49_2 {

    public int nthUglyNumber(int n) {

        int i2=0,i3=0,i5=0;

        int now = 0;

        int[] nums = new int[n];

        nums[0] = 1;

        for(int i=1;i<n;i++){

            nums[i] = Math.min(nums[i2] * 2, Math.min(nums[i3] * 3, nums[i5] * 5));

            if(nums[i] == nums[i2] * 2)

                i2++;

            if(nums[i] == nums[i3] * 3)

                i3++;

            if(nums[i] == nums[i5] * 5)

                i5++;

        }

        return nums[n-1];

    }

}

巴特西

剑指 Offer 49. 丑数 + 小根堆 + 动态规划

剑指 Offer 49. 丑数

Offer_49

题目详情

解法一：小根堆+哈希表/HashSet

解法二：动态规划

最新文章

热门文章