丑数 二 ---- 设计一个算法，找出只含素因子`2`，`3`，`5` 的第 n 小的数

标签：block   lan   一个   要求   条件   控制   java   比较   class   

题目 -丑数 二

设计一个算法，找出只含素因子2，3，5 的第 n 小的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

我们可以认为1也是一个丑数

分析

根据题目可得，丑数即由若干个2、3、5相乘所的到的数。可以写成

2^a + 3^b + 5^c

a,b,c可以取随意自然数

再进一步分析，可以得到每个丑数都存在另一个丑数乘以2、3、5中的一个数，与之相等。

题目要求要第n个小的丑数。

第一种思路

第一种思路，第n小的丑数，那就把丑数都列出来从小到大排序即可，进而推演，即找出最小的丑数，然后将之乘以2、3、5，然后将结果与之前的所有丑数进行对比，再找出最小的丑数，进行一个循环，最后将第n次选出的最小的丑数返回。

这种思路每次都要遍历一遍数组，效率过慢。

第二种思路

把所有除了1的丑数分为三组，第一组是最小的丑数乘以2的，第二组是最小的丑数乘以3的，第三组是最小的丑数乘以5的。这样的话没组的数字都是有序的，我们只需将每组中的最小的进行比较，然后将最小的踢出自己的数组，然后用最小的数分别乘以2、3、5，将乘出的数分别放回三个数组。

例：

2: 2，4，6，10....

3: 3，6，9，15....

5: 5，10，15，20....

代码实现如下：

 public int nthUglyNumber(int n) {
        // write your code here
        
        List l2 = new ArrayList();
        List l3 = new ArrayList();
        List l5 = new ArrayList();
        
        int min = 1;
        int f1 = 0;
        int f2 = 0;
        int f3 = 0;
        
        for(int i = 1; i

或者是下面这种代码实现方式：

将数都放在一个数组中，用f1，f2，f3来控制2，3，5组的推进。

public int nthUglyNumber(int n) {
        // write your code here
        
        List  ints = new ArrayList();
        int f1 = 0;
        int f2 = 0;
        int f3 = 0;
        
        
        ints.add(1);
        for(int i = 1; i

丑数 二 ---- 设计一个算法，找出只含素因子`2`，`3`，`5` 的第 n 小的数

标签：block   lan   一个   要求   条件   控制   java   比较   class   

原文地址：https://www.cnblogs.com/smren/p/12864786.html