题目：
 
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。
 
求按从小到大的顺序的第N个丑数。
 
思路：某个丑数肯定是前面丑数的2,3,5倍数。只需要从前往后生成即可。1,2,3,4,5,6,8,9,10,12,15，。。。。。。。
 

 
 
代码：
 
 
public class Solution {
    public int min(int a,int b,int c){
        int min=(a<b)?a:b;
        return (min<c)?min:c;
    }
    public int GetUglyNumber_Solution(int index) {
        //1,2,3,4,5....
        if(index<=0)
            return 0;
        int[] a=new int[index];
        a[0]=1;
        int multi1=0;
        int multi2=0;
        int multi3=0;
        for(int i=1;i<a.length;i++){
            int min=min(a[multi1]*2,a[multi2]*3,a[multi3]*5);
            a[i]=min;
            while(a[multi1]*2<=min)
                multi1++;
            while(a[multi2]*3<=min)
                multi2++;
            while(a[multi3]*5<=min)
                multi3++;
                
        }
        
        return a[a.length-1];
    }
}

 

 

      这是一个很好的算法题，解法类似于快速排序的整理方法。同时，更为值得注意的是这道题是 人人网2014校园招聘的笔试题，下面首先对题目进行描述：
      给出一个有序数组，另外给出第三个数，问是否能在数组中找到两个数，这两个数之和等于第三个数。
      我们首先看到第一句话，这个数组是有序的，所以，我们可以定义两个指针，一个指向数组的第一个元素，另一个指向应该指向的位置（这个需要看具体的实现和数组给定的值），首先计算两个位置的和是否等于给定的第三个数，如果等于则算法结束，如果大于，则尾指针向头指针方向移动，如果小于，则头指针向尾指针方向移动，当头指针大于等于尾指针时算法结束，没有找到这样的两个数。
      它看起来就好像下面这张图一样：


      下面给出具体的实现：

#include <stdio.h>

int judge(int *a, int len, int k, int *num1, int *num2);

int main(int argc, char **argv)
{
	int test_array[] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
	int result = -1;
	int num1, num2;
	result = judge(test_array, sizeof(test_array) / sizeof(int), 12, &num1, &num2);
	if(result == 0)
	{
		printf("%d\t%d\n", num1, num2);
	}
	else if(result == -1)
	{
		printf("can't find");
	}
	else
	{
		printf("error");
	}
}

int judge(int *a, int len, int k, int *num1, int *num2)
{
	int *low = NULL;
	int *high = NULL;
	int i = 0;
	int result = -1;
	if(a == NULL || len < 2)
	{
		return result;
	}
	if(a[0] >= k)
	{
		return result;
	}
	while(a[i] <= k && i < len)
	{
		i++;
	}
	low = a;
	high = a + i - 1;
	while(low  < high)
	{
		*num1 = *low;
		*num2 = *high;
		if((*low + *high) == k)
		{
			result = 0;
			break;
		}
		else if((*low + *high) > k)
		{
			high--;
		}
		else if((*low + *high) < k)
		{
			low++;
		}
	}
	return result;
}


      这样就以高效的方法得到了结果。

 
 
参考《剑指Offer》
 
 
题目：
 
我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
 
分析
 
常规解法
 
第一反应，我们肯定从1开始遍历，一直到找到第1500个丑数为止，如下：
 
bool isUgly(int number)  
{  
    while (number%2==0)  
        number = number/2;  
    while (number%3==0)  
        number = number/3;  
    while (number%5==0)  
        number = number/5;  
    return (number==1)?true:false;  
}  

 
高效解法：
 
前面算法之所以效率低，是因为不管一个数是不是丑数都遍历了，我们要尝试找一个只需要计算丑数的方法。
 首先，我们再次明确丑数的定义：
 
 
 
丑数是只包含因子2、3和5的数。
 
 
那么很容易我们就可以想到，位于前面的丑数，定然是后面的丑数的因子。比如2是4、6、30的因子，3是6、15、27、30的因子。
 那么，我们可以通过前面的丑数乘以2、3、5来计算出后面的丑数。
 而我们要解决的最主要的问题就是丑数的排序问题。
 
 
 
解决方法：每次找出生成的丑数中大于M的最小值。
 
 
首先，我们把已有的丑数都乘以2，找到其中第一个大于M的结果，记作M2。同样的方法乘以3、5，找到的结果记作M3、M5。
 最终找到M2、M3、M5中的最小值，就是新生成的最大的丑数，记作新的M。
 
当然，如果每次都需要对丑数从头到尾的乘以和判断效率是很低的，我们可以用一个数T来记录M的下标。
 比如T2，即为M2的下标，在它之前的每一个值乘以2都会小于M，在它之后的每一个值乘以2都会大于M。每次新生成M的时候我们再更新这个T2。
 这样我们每次计算M2（乘以2后第一个大于M的数）的时候，只需要让T2后面的一个数乘以2即可了。
 T3、T5的生成方式一样。
 #代码
 
#include<iostream>

using namespace std;

int Min(int n1,int n2,int n3)
{
    int min=(n1<n2)?n1:n2;
    min=(min<n3)?min:n3;
    return min;
}

int Solution(int n)
{
    if(n<=0)
        return 0;

    int u[n];
    u[0]=1;//1为第一个丑数

    int t2=0;//记录M2的下标
    int t3=0;
    int t5=0;

    for(int i=1;i<n;i++)
    {
        while(u[t2]*2<=u[i-1])//查找到新的M2，即乘以2后第一个大于M的数
            t2++;
        while(u[t3]*3<=u[i-1])
            t3++;
        while(u[t5]*5<=u[i-1])
            t5++;
        int min=Min(u[t2]*2,u[t3]*3,u[t5]*5);
        u[i]=min;
    }

    return u[n-1];
}

int main()
{
    cout<<Solution(1500)<<endl;

    return 0;
}

 
结果
 

题目：
 
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 
解题思路：选定第一个丑数1，根据丑数的定义，可知以后的丑数必然是在1的基础上乘以2，乘以3，乘以5，因此可以得出三个丑数，从中选择最小的一个添加到list列表中，之后若list中的丑数与得出的三个丑数中的一个或两个相等，将对应的下标后移，具体代码如下所示：
 
import java.util.ArrayList;
 
public class Solution {
     public int GetUglyNumber_Solution(int index) {
         if(index<=0){
             return 0;
         }
         ArrayList<Integer> list=new ArrayList<>();
         list.add(1);
         int t2=0,t3=0,t5=0;//对应的下标
         while(list.size()<index){
             int m2=list.get(t2)*2;
             int m3=list.get(t3)*3;
             int m5=list.get(t5)*5;
             int min=Math.min(m2,Math.min(m3,m5));
             list.add(min);
 
            //若列表中存在，则对应的得出此丑数的下标后移
             if(min==m2){
                 t2++;
             }
             if(min==m3){
                 t3++;
             }
             if(min==m5){
                 t5++;
             }
         }
         return list.get(list.size()-1);
     }
 }