丑数知多少？

佚名 6年前 (2019-05-16) 随笔 2179人围观抢沙发百度已收录

题目

我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。

动态规划分析

假设这个数为 n，如果n是丑数，只有三种可能：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

n是能整除2，即 n % 2 == 0，且 n/2 是丑数。
n % 3 == 0 且 n/3是丑数。
n % 5 == 0且 n / 5是丑数。

三种可能只要满足其中一种，就可以确认是丑数了。即后面的丑数是由前一个丑数乘以2，3，5中的一个得来

状态转移方程

u2、u3、u5代表2，3，5倍数的队列。

详细代码

#include <cstdio>

/* 丑数判断 */
bool IsUgly(int number)
{
    while(number % 2 == 0)
        number /= 2;
    while(number % 3 == 0)
        number /= 3;
    while(number % 5 == 0)
        number /= 5;

    return (number == 1) ? true : false;
}

/* 算法1：逐个判断每个整数是不是丑数，简洁直观但每个整数都需要计算，不够高效*/
int GetUglyNumber_Solution1(int index)
{
    if(index <= 0)
        return 0;

    int number = 0;
    int uglyFound = 0;
    while(uglyFound < index)
    {
        ++number;

        if(IsUgly(number))
            ++uglyFound;
    }

    return number;
}

/* 3个数中的最小值 */
int Min(int number1, int number2, int number3)
{
    int min = (number1 < number2) ? number1 : number2;
    min = (min < number3) ? min : number3;

    return min;
}

/* 解法2：创建数组保存已经找到的丑数，用空间换取时间 
 * 动态规划，对于第i个数，它一定是之前已存在数的2倍，3倍或5倍
 */
int GetUglyNumber_Solution2(int index)
{
    if(index <= 0)
        return 0;

    int *pUglyNumbers = new int[index];
    pUglyNumbers[0] = 1;
    int nextUglyIndex = 1;

    int *pMultiply2 = pUglyNumbers;
    int *pMultiply3 = pUglyNumbers;
    int *pMultiply5 = pUglyNumbers;

    while(nextUglyIndex < index)
    {
        int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);
        pUglyNumbers[nextUglyIndex] = min;

        while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
            ++pMultiply2;
        while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
            ++pMultiply3;
        while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
            ++pMultiply5;

        ++nextUglyIndex;
    }

    int ugly = pUglyNumbers[nextUglyIndex - 1];
    delete[] pUglyNumbers;
    return ugly;
}


// ====================测试代码====================
void Test(int index, int expected)
{
    if(GetUglyNumber_Solution1(index) == expected)
        printf("solution1 passed\n");
    else
        printf("solution1 failed\n");

    if(GetUglyNumber_Solution2(index) == expected)
        printf("solution2 passed\n");
    else
        printf("solution2 failed\n");
}

int main(int argc, char* argv[])
{
    Test(1, 1);

    Test(2, 2);
    Test(3, 3);
    Test(4, 4);
    Test(5, 5);
    Test(6, 6);
    Test(7, 8);
    Test(8, 9);
    Test(9, 10);
    Test(10, 12);
    Test(11, 15);

    Test(1500, 859963392);

    Test(0, 0);

    return 0;
}

C++

# -*- coding:utf-8 -*-

import sys

# 3个队列，分别保存2，3，5 的倍数，依次取最小值，然后添加。
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        #2,3,5
        if index <=0 :
            return 0
        if index==1:
            return 1
        queue2 = []
        queue3 = []
        queue5 = []
        queue2.append(2)
        queue3.append(3)
        queue5.append(5)
        val = 0
        for i in range(2,index+1):
            v2 = queue2[0] if len(queue2)!=0 else sys.maxint
            v3 = queue3[0] if len(queue3) !=0 else sys.maxint
            v5 = queue5[0] if len(queue5) !=0 else sys.maxint
            val = min(v2,v3,v5)
            if val == v2:
                queue2.pop(0)
                queue2.append(val*2)
                queue3.append(val*3)
            elif val ==v3:
                queue3.pop(0)
                queue3.append(val*3)
            else:
                queue5.pop(0)
            queue5.append(val *5)
 
        return val
 
print(Solution().GetUglyNumber_Solution(7))