Ugly Number II (M)
題目
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1is typically treated as an ugly number.ndoes not exceed 1690.
題意
找到第n個因數只有2、3、5的整數，
思路
- 自底向上生成第n個丑陋數：每個丑陋數都可以由之前的某一個丑陋數乘2或3或5得到，因此記錄下2、3、5要乘的下一個丑陋數的下標，每一次從得到的三個數中選取最小的一個作為新的丑陋數加入串列中，并根據這個值將2、3、5要乘的下一個下標往后挪一位，如下圖示例：
- 堆：用小頂堆存盤丑陋數，每次取堆頂的數x作為最新的丑陋數，并將所有與x相同的數除去，最后再往堆里存入2x、3x、5x，重復操作n次后得到的就是第n個丑陋數，(注意這種方法每次都是用最新的丑陋數去乘2、3、5，因此可能出現int越界的情況，所以堆必須用long)
代碼實作
Java
迭代
class Solution {
public int nthUglyNumber(int n) {
List<Integer> list = new ArrayList<>();
list.add(1);
int times2pos = 0, times3pos = 0, times5pos = 0;
while (list.size() < n) {
int times2 = list.get(times2pos) * 2;
int times3 = list.get(times3pos) * 3;
int times5 = list.get(times5pos) * 5;
int min = Math.min(Math.min(times2, times3), times5);
if (min == times2) times2pos++;
if (min == times3) times3pos++;
if (min == times5) times5pos++;
list.add(min);
}
return list.get(list.size() - 1);
}
}
堆
class Solution {
public int nthUglyNumber(int n) {
Queue<Long> heap = new PriorityQueue<>();
heap.offer(1l);
int count = 0;
long ans = 0;
while (count != n) {
ans = heap.poll();
while (!heap.isEmpty() && heap.peek() == ans) {
heap.poll();
}
heap.offer(ans * 2);
heap.offer(ans * 3);
heap.offer(ans * 5);
count++;
}
return (int)ans;
}
}
JavaScript
/**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function (n) {
let list = [1]
let pos2 = 0, pos3 = 0, pos5 = 0
while (list.length < n) {
let times2 = list[pos2] * 2
let times3 = list[pos3] * 3
let times5 = list[pos5] * 5
let min = Math.min(times2, times3, times5)
if (min === times2) pos2++
if (min === times3) pos3++
if (min === times5) pos5++
list.push(min)
}
return list[n - 1]
}
參考
[LeetCode] 264. Ugly Number II 丑陋數之二
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27704.html
標籤：其他