[LeetCode] 264. Ugly Number II

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:

1 is typically treated as an ugly number.
n does not exceed 1690.

丑数II。题目问的是求出第N个丑陋数字。

思路是需要按规则求出前N-1个丑陋数字才行。首先第一个丑数是1，然后会用到三个pointer，分别代表2的倍数，3的倍数和5的倍数。1之后的每个丑数，是当前丑数分别乘以2,3和5的最小值。

时间O(n)

空间O(n)

JavaScript实现

 1 /**
 2  * @param {number} n
 3  * @return {number}
 4  */
 5 var nthUglyNumber = function(n) {
 6     let nums = new Array(n);
 7     let index2 = 0,
 8         index3 = 0,
 9         index5 = 0;
10     nums[0] = 1;
11     for (let i = 1; i < n; i++) {
12         nums[i] = Math.min(nums[index2] * 2, Math.min(nums[index3] * 3, nums[index5] * 5));
13         if (nums[i] === nums[index2] * 2) index2++;
14         if (nums[i] === nums[index3] * 3) index3++;
15         if (nums[i] === nums[index5] * 5) index5++;
16     }
17     return nums[n - 1];
18 };

Java实现

 1 class Solution {
 2     public int nthUglyNumber(int n) {
 3         int[] nums = new int[n];
 4         int index2 = 0, index3 = 0, index5 = 0;
 5         nums[0] = 1;
 6         for (int i = 1; i < nums.length; i++) {
 7             nums[i] = Math.min(nums[index2] * 2, Math.min(nums[index3] * 3, nums[index5] * 5));
 8             if (nums[i] == nums[index2] * 2)
 9                 index2++;
10             if (nums[i] == nums[index3] * 3)
11                 index3++;
12             if (nums[i] == nums[index5] * 5)
13                 index5++;
14         }
15         return nums[n - 1];
16     }
17 }

LeetCode 题目总结