Swift学习——寻找丑数

参考自：http://www.cnblogs.com/python27/archive/2011/11/24/2261550.html

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

　　分析：寻找一个数是不是满足某种数（质数，水仙数）等，最简单的方法就是遍历，对于任意一个丑数必定可以写成2^m*3^n*5^p，因而对于一个丑数，只含有2，3，5因子，也就意味着该数number%2==0；number%3==0；number%5==0，如果一个数能被2整除，我们就连续除以2；能被3整除，我们就连续除以3；能被5整除，我们就连续除以5；如果最后得到1，则该数是素数，否则是丑数。

　　代码如下：

func isUglyNumber(number:Int)->Bool
{
    var number1 = number
    while number1 % 2 == 0
    {
        number1 /= 2
    }
    while number1 % 3 == 0
    {
        number1 /= 3
    }
    while number1 % 5 == 0
    {
        number1 /= 5
    }
    if number1 == 1
    {
        return true
    }
    else{
        return false
    }
}


func getUglyNumber1(index:Int)->Int{
    if index <= 0{
        return 0
    }
    var number:Int = 0
    var count:Int = 0
    while(count < index)
    {
        ++number
        if isUglyNumber(number){
            ++count
        }
    }
    return number
}

上面计算中主要的不足在于，逐一遍历，这样对于不是丑数的数的判断会造成大量的时间浪费，如果能够根据已经计算好的丑数，计算出下一个丑数就可以避免这种情况，实现从丑数到丑数的高效算法，根据定义可知，后面的丑数肯定是前面已知丑数乘以2，3，5得到的。

　　我们假设一个数组中已经有若干丑数，并且这些丑数是按顺序排列的，我们把现有的最大丑数记为max，则下一个丑数肯定是前面丑数乘以2，3，5得到的。不妨考虑乘以2得到的情况，我们把数组中的每一个数都乘以2，由于原数组是有序的，因为乘以2后也是有序递增的，这样必然存在一个数M2，它前面的每一个数都是小于等于max，而包括M2在内的后面的数都是大于max的，因为我们还是要保持递增顺序，所以我们取第一个大于max的数M2。同理对于乘以3的情况，可以取第一个大于max的数M3，对于乘以5的情况，可以取第一个大于max的数M5。

　　最终下一个丑数取:min{M2,M3,M5}即可
　　（相当于将之前得到的丑数放到一个数组array里，然后分别将数组array里的丑数乘以2，将其与数组array的最后一个丑数b相比，一旦大于b，就称其为上述中的M2，同理可得M3，M5）
　　代码如下：
　　

func getUglyNumber2(index:Int)->Int{
    var uglyNum:Int = 1
    if index <= 0{
        return 0
    }
    var uglyArray:Array<Int> = [1]
    var m2Array:Array<Int> = Array()
    var m3Array:Array<Int> = Array()
    var m5Array:Array<Int> = Array()
    while uglyArray.count < index{
        var m2:Int = 0
        var m3:Int = 0
        var m5:Int = 0
        m2Array = uglyArray
        m3Array = uglyArray
        m5Array = uglyArray
        for (index,value) in enumerate(m2Array){
            m2Array[index] = value*2
            if m2Array[index] > uglyArray.last{
                m2 = m2Array[index]
                break
            }
        }
        for (index,value) in enumerate(m3Array){
            m3Array[index] = value*3
            if m3Array[index] > uglyArray.last{
                m3 = m3Array[index]
                break
            }
        }
        for (index,value) in enumerate(m5Array){
            m5Array[index] = value*5
            if m5Array[index] > uglyArray.last{
                m5 = m5Array[index]
                break
            }
        }

        uglyNum = min(m2,m3,m5)
        uglyArray.append(uglyNum)
    }
    return uglyNum
}

在此感谢http://www.cnblogs.com/python27/的每日一算法的分享

Swift学习——寻找丑数

猜你在找的Swift相关文章