LeetCode--Ugly Number II

忘是亡心i 2022-08-17 14:09 16阅读 0赞

**Problem:**

> Write a program to find the n-th ugly number.  
> Ugly numbers are positive numbers whose prime factors only include 2,  
> 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of  
> the first 10 ugly numbers.  
> Note that 1 is typically treated as an ugly number.

**Anlysis:**  
题意：求第n个丑数（丑数的理解可以查看[http://blog.csdn.net/u010305706/article/details/50033219][http_blog.csdn.net_u010305706_article_details_50033219]）

由于考虑到运算效率和超时问题需要考虑更为高效的算法，分析如下：

Anwser1算法非常直观，代码也非常简洁，但最大的问题我们每个整数都需要计算。即使一个数字不是丑数，我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高。

接下来我们换一种思路来分析这个问题，试图只计算丑数，而不在非丑数的整数上花费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。

这种思路的关键在于怎样确保数组里面的丑数是排好序的。我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果，记为M2。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5三个数的最小者。

> (1) 1×2, 2×2, 3×2, 4×2, 5×2, …  
> (2) 1×3, 2×3, 3×3, 4×3, 5×3, …  
> (3) 1×5,2×5, 3×5, 4×5, 5×5, …

前面我们分析的时候，提到把已有的每个丑数分别都乘以2、3和5，事实上是不需要的，因为已有的丑数是按顺序存在数组中的。对乘以2而言，肯定存在某一个丑数T2，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T2。对乘以3和5而言，存在着同样的T3和T5。  
**Anwser1：**  
（但是这个方法严重超时，没有A，在这里只是把一般想法列出来）

public class Solution {
        public int nthUglyNumber(int n) {
            int number=0;
            while(n>0){
            if (isUgly(number++)) n--;
            }
            return number-1;
        }
        public boolean isUgly(int num){
            if (num == 0) return false;
            else if (num ==1) return true;
            else{
                while(num % 2 == 0) num /=2;
                while(num % 3 == 0) num /=3;
                while(num % 5 == 0) num /=5;
                return num==1;
            }
        }
    }

**Anwser2：**

public class Solution {
        public int nthUglyNumber(int n) {
            int next=1;
            int M2=0,M3=0,M5=0;//M2,M3,M5分别代表乘以2,3,5的当前位置
            int[] uglynums= new int[n];
            uglynums[0]=1;
            int min=1;
            while(next < n){
                min= Min(uglynums[M2]*2,uglynums[M3]*3,uglynums[M5]*5);
                uglynums[next] = min;
                if(min ==uglynums[M2]*2) M2++;
                if (min == uglynums[M3]*3) M3++;//注意换成else if不可以，这样没有考虑相等的情况
                if (min == uglynums[M5]*5) M5++;//注意换成else if不可以，这样没有考虑相等的情况
                next++;
            }
            return min;
        }
        public static int Min(int i,int j,int k){
            int m ;
            m = i > j ? j:i;
            return m > k ? k:m;
        }
    }

注意以上代码中的if 不能写成else if ，代码中的核心部分是先选出最小的丑数，然后根据这个丑数确定相应的乘以2，3，5的记录位置移动，在c++中可以用指针。

[http_blog.csdn.net_u010305706_article_details_50033219]: http://blog.csdn.net/u010305706/article/details/50033219