JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

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.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Code

class Solution {
    public int nthUglyNumber(int n) {
        int[] res = new int[n];
        res[0] = 1;
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;

        for(int i = 1; i < n; i++) {
            res[i] = Math.min(res[i2] * 2, Math.min(res[i3] * 3, res[i5] * 5));
            if(res[i] == res[i2] * 2) i2 += 1;
            if(res[i] == res[i3] * 3) i3 += 1;
            if(res[i] == res[i5] * 5) i5 += 1;
        }

        return res[n - 1];
    }
}

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [0] * n
        res[0] = 1
        i2 = 0
        i3 = 0
        i5 = 0

        for i in range(1, n):
            res[i] = min(res[i2] * 2, min(res[i3] * 3, res[i5] * 5))
            if res[i] == res[i2] * 2:
                i2 += 1

            if res[i] == res[i3] * 3:
                i3 += 1

            if res[i] == res[i5] * 5:
                i5 += 1

        return res[-1]