Nuggets team number online, help you Offer impromptu! Click for details

The title

Given an integer n, please find and return the NTH ugly number.

Ugly numbers are positive integers that contain only prime factors 2, 3, and/or 5.

 

Example 1:

Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is a sequence consisting of the first 10 ugly numbers.

Tip:

1 <= n <= 1690

Source: LeetCode

Link: leetcode-cn.com/problems/ug…

Thought analysis

  • The problem is easy to understand, but writing clean code is difficult. You can try to write it yourself. Clear your head, find the smallest ugly number of each, and finish sorting.

code

public class DayCode {
    public static void main(String[] args) {
        int num = 6;
        int ans = new DayCode().nthUglyNumber(num);
        System.out.println("ans is " + ans);
    }

    /** * Time complexity O(n) * Space complexity O(1) *@param n
     * @return* /
    public int nthUglyNumber(int n) {
        int size = 1690;
        int[] nums = new int[size];
        nums[0] = 1;
        int ugly = 0, i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < size; i++ ) {
            ugly = Math.min(Math.min(nums[i2] * 2, nums[i3] * 3), nums[i5] * 5);
            nums[i] = ugly;
            if (ugly == nums[i2] * 2) {
                i2++;
            }
            if (ugly == nums[i3] * 3) {
                i3++;
            }
            if (ugly == nums[i5] * 5) { i5++; }}return nums[n-1]; }}Copy the code

conclusion

  • Today’s daily problem, and yesterday’s ugly number formed a response, a bit more complex than yesterday, practice the five poison god palm! The n = 1690 condition here is important, and we can use it directly to initialize the array.
  • Stick to the daily question, come on!