共计 1391 个字符,预计需要花费 4 分钟才能阅读完成。
一、题目形容:
给你一个整数 n,请你找出并返回第 n 个 丑数。
丑数 就是只蕴含质因数 2、3 和 / 或 5 的正整数
二、思路剖析:
三指针
1.2,3,5 别离对应指针 i2,i3,i5, 遍历找到以后指针
2. 挪动 i 对于的以后指针,并记录后果
3. 找到数组最初一位即是第 n 个丑数
三、AC 代码:
javascript
/**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function (n) {
let i2 = 0,// 2 对应的指针
i3 = 0,// 3 对应的指针
i5 = 0,// 5 对应的指针
dp = [1] //dp 数组
for (let i = 1; i < n; i++) {
// 计算 i 对应以后那个指针
let min = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
// 指针别离向前挪动
if (min === dp[i2] * 2) i2++
if (min === dp[i3] * 3) i3++
if (min === dp[i5] * 5) i5++
dp[i] = min
}
return dp[dp.length - 1]
};
Python
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
i2,i3,i5,dp = 0,0,0,[1]
for _ in range(1,n):
# 计算 i 对应以后那个指针
minMars = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
# 指针别离向前挪动
if minMars == dp[i2] * 2:
i2 = i2+1
if minMars == dp[i3] * 3:
i3 = i3+1
if minMars == dp[i5] * 5:
i5 = i5+1
dp.append(minMars)
return dp[len(dp) - 1]
Typescript
function nthUglyNumber(n: number): number {
let i2:number = 0,// 2 对应的指针
i3:number = 0,// 3 对应的指针
i5:number = 0,// 5 对应的指针
dp:number[] = [1] //dp 数组
for (let i = 1; i < n; i++) {
// 计算 i 对应以后那个指针
let min = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
// 指针别离向前挪动
if (min === dp[i2] * 2) i2++
if (min === dp[i3] * 3) i3++
if (min === dp[i5] * 5) i5++
dp[i] = min
}
return dp[dp.length - 1]
};
Go
func nthUglyNumber(n int) int {dp := make([]int, n+1)
dp[1] = 1
i2, i3, i5 := 1, 1, 1
for i := 2; i <= n; i++ {
// 计算 i 对应以后那个指针
x2, x3, x5 := dp[i2]*2, dp[i3]*3, dp[i5]*5
dp[i] = min(min(x2, x3), x5)
if dp[i] == x2 {i2++}
if dp[i] == x3 {i3++}
if dp[i] == x5 {i5++}
}
return dp[n]
}
// 因为 go 语言外面没有 min() 函数,本人构建一个
func min(a, b int) int {
if a > b {return b}
return a
}
四、总结:
1. 三指针计算以后 i 对应的丑数,记录丑数到数组,取最初面一位。持续加油!
正文完