一、题目描述：
给你一个整数 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对应的丑数，记录丑数到数组，取最后面一位。继续加油！
