经典的找第几个丑数是啥

大一小孩都会

https://leetcode.com/problems/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. 1 is typically treated as an ugly number.
  2. n does not exceed 1690.

思路：dp找的时候，当前的丑数肯定是前面某个的丑数+2/3/5得到的

那么递推即可 pos记录上轮找的时候2，3，5到第几个了，之前的就不用再算了

class Solution {//2, 3, 2*2=4, 5, 2*3=6, 3*3=9, 2*5=10, 3*5=15, 5*5=25
public:
    int nthUglyNumber(int n) {
        int ans[2000];
        ans[1] = 1;
        ans[2] = 2;
        ans[3] = 3;
        ans[4] = 4;
        int cnt = 4;
        int pos2 = 1, pos3 = 1, pos5 = 1;
        while(cnt <= n) {
            int k ;
            for (int i = pos2; i < cnt ;i ++) {
                if (ans[i] * 2 > ans[cnt-1]) {
                    pos2 = i;
                    k = ans[i] * 2;
                    break;
                }
            }
            for (int i = pos3; i < cnt ;i ++) {
                if (ans[i] * 3 > ans[cnt-1]) {
                    pos3 = i;
                    k = min(k, ans[i] * 3);
                    break;
                }
            }
            for (int i = pos5; i < cnt ;i ++) {
                if (ans[i] * 5 > ans[cnt-1]) {
                    pos5 = i;
                    k = min(k, ans[i] * 5);
                    break;
                }
            }
            ans[cnt++] = k;
        }
        return ans[n];
    }
};