寻找第n个丑数

xiaoxiao2021-03-01  13

Description

Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

 

通过空间代价来提升时间复杂度。

创建一个数组,长度为n,根据n位的丑数是前面的丑数乘2、乘3或乘5所得,比较所得最小的数就是最新的丑数。

算过一次之后,该因子的基数加一,避免重复计算。

 

public class Solution {     /**      * @param n: An integer      * @return: the nth prime number as description.      */     public int nthUglyNumber(int n) {         // write your code here         int[] ugly = new int[n];         ugly[0] = 1;         int nextUglyIndex = 1;

        int mul2 = 0;         int mul3 = 0;         int mul5 = 0;         int min = 0;         while(nextUglyIndex<n){             min = compare_min(ugly[mul2]*2,ugly[mul3]*3,ugly[mul5]*5);             ugly[nextUglyIndex] = min;             while(ugly[mul2]*2<=ugly[nextUglyIndex]){                 mul2++;             }             while(ugly[mul3]*3<=ugly[nextUglyIndex]){                 mul3++;             }             while(ugly[mul5]*5<=ugly[nextUglyIndex]){                 mul5++;             }

            nextUglyIndex++;

        }         int result = ugly[n - 1];         return result;     }     public int compare_min(int a,int b,int c){         if(a<=b){             if(a<=c)                 return a;             return c;         }else if(c<=b){             return c;         }         return b;     } }

转载请注明原文地址: https://www.6miu.com/read-4200278.html

最新回复(0)