Java代码如何实现求第N个丑数?实现和思路分享

KLQ 2020-04-16 11:48:50 java常见问答 5743

你知道用Java代码实现求第N个丑数的方法吗?下面给大家带来的就是以上相关内容,包含了具体的实现实例以及相关思路整理。

题目:

将只包括了质因子2、3和5的数称为丑数。

例:

6、8都是丑数,14不是(14包含质因子7)

习惯上面将1当成是第一个丑数。

求按从小到大的顺序的第N个丑数。

思路1

代码实现:

class Solution
{
    public: //别人的代码就是精简,惭愧啊,继续学习。
        int GetUglyNumber_Solution(int index)
        {
            if (index < 7) return index;
            vector < int > res(index);
            res[0] = 1;
            int t2 = 0, t3 = 0, t5 = 0, i;
            for (i = 1; i < index; ++i)
            {
                res[i] = min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5));
                if (res[i] == res[t2] * 2) t2++;
                if (res[i] == res[t3] * 3) t3++;
                if (res[i] == res[t5] * 5) t5++;
            }
            return res[index - 1];
        }
};

思路2:

依据丑数的定义,一个丑数的因子只有2,3,5,那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z,也就是说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到,那么我们从1开始乘以2,3,5,就得到2,3,5三个丑数,在从这三个丑数出发乘以2,3,5就得到4,6,10,6,9,15,10,15,25九个丑数,我们发现这种方***得到重复的丑数,而且我们题目要求第N个丑数,这样的方法得到的丑数也是无序的。

那么我们可以维护三个队列:

(1)丑数数组: 1

乘以2的队列:2

乘以3的队列:3

乘以5的队列:5

选择三个队列头最小的数2加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;

(2)丑数数组:1,2

乘以2的队列:4

乘以3的队列:3,6

乘以5的队列:5,10

选择三个队列头最小的数3加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;

(3)丑数数组:1,2,3

乘以2的队列:4,6

乘以3的队列:6,9

乘以5的队列:5,10,15

选择三个队列头里最小的数4加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;

(4)丑数数组:1,2,3,4

乘以2的队列:6,8

乘以3的队列:6,9,12

乘以5的队列:5,10,15,20

选择三个队列头里最小的数5加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;

(5)丑数数组:1,2,3,4,5

乘以2的队列:6,8,10,

乘以3的队列:6,9,12,15

乘以5的队列:10,15,20,25

选择三个队列头里最小的数6加入丑数数组,但我们发现,有两个队列头都为6,所以我们弹出两个队列头,同时将12,18,30放入三个队列;

疑问:

1.为什么分三个队列?

丑数数组里的数一定是有序的,因为我们是从丑数数组里的数乘以2,3,5选出的最小数,一定比以前未乘以2,3,5大,同时对于三个队列内部,按先后顺序乘以2,3,5分别放入,所以同一个队列内部也是有序的;

2.为什么比较三个队列头部最小的数放入丑数数组?

因为三个队列是有序的,所以取出三个头中最小的,等同于找到了三个队列所有数中最小的。

实现思路:

我们没有必要维护三个队列,只需要记录三个指针显示到达哪一步;“|”表示指针,arr表示丑数数组;

(1)1

|2

|3

|5

目前指针指向0,0,0,队列头arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5

(2)1 2

2 |4

|3 6

|5 10

目前指针指向1,0,0,队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5

(3)1 2 3

2| 4 6

3 |6 9

|5 10 15

目前指针指向1,1,0,队列头arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5

………………

代码实现:

class Solution
{
    public:
        int GetUglyNumber_Solution(int index)
        {
            // 0-6的丑数分别为0-6
            if (index < 7) return index;
            //p2,p3,p5分别为三个队列的指针,newNum为从队列头选出来的最小数
            int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
            vector < int > arr;
            arr.push_back(newNum);
            while (arr.size() < index)
            {
                //选出三个队列头最小的数
                newNum = min(arr[p2] * 2, min(arr[p3] * 3, arr[p5] * 5));
                //这三个if有可能进入一个或者多个,进入多个是三个队列头最小的数有多个的情况
                if (arr[p2] * 2 == newNum) p2++;
                if (arr[p3] * 3 == newNum) p3++;
                if (arr[p5] * 5 == newNum) p5++;
                arr.push_back(newNum);
            }
            return newNum;
        }
};

思路3:

我们只用比较3个数:用于乘2的最小的数、用于乘3的最小的数,用于乘5的最小的。

代码实现:

public int GetUglyNumber_Solution2(int n)
{
    if (n <= 0) return 0;
    ArrayList < Integer > list = new ArrayList < Integer > ();
    list.add(1);
    int i2 = 0, i3 = 0, i5 = 0;
    while (list.size() < n) //循环的条件
    {
        int m2 = list.get(i2) * 2;
        int m3 = list.get(i3) * 3;
        int m5 = list.get(i5) * 5;
        int min = Math.min(m2, Math.min(m3, m5));
        list.add(min);
        if (min == m2) i2++;
        if (min == m3) i3++;
        if (min == m5) i5++;
    }
    return list.get(list.size() - 1);
}

以上就是如何实现求第N个丑数的实现和思路了,更多的Java实例,可以继续的来本站了解。