牛客_找寻第n个丑数

题目描述

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

分析：

一个丑数的质因子只有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个丑数，这样的方法得到的丑数也是无序的。

丑数数组里的数一定是有序的，因为我们是从丑数数组里的数乘以2,3,5选出的最小数，一定比以前未乘以2,3,5大，同时对于三个队列内部，按先后顺序乘以2,3,5分别放入，所以同一个队列内部也是有序的。因为三个队列是有序的，所以取出三个头中最小的，等同于找到了三个队列所有数中最小的。在维护这个队列比较麻烦，所以只需要将比较的三个队列中最小的数字赋给一个单独的数组既可，这样就保证了这个数组中的数都是依次递增。

package com.bjut;

import java.util.Vector;
public class GetUglyNumber_Solution {
    public static void main(String[] args) {
        System.out.println("输出的第n个元素为"+GetUglyNumber_Solution(10));
    }
    public static  int GetUglyNumber_Solution(int index) {
        if(index<=0){
            return 0;
        }
        //通过对指数因子的判定可以得到在排序在前6个数字都是数字本身
        if(index<7){
            return index;
        }
        //定义p2,p3,p5分别代表由质因子2、3、5的队列中产生的数字
        //newNum为从队列中选出来的最小值，作为当前顺序排序的的数字，起始位1
        int p2=0,p3=0,p5=0,newNum=1;
        //Vector 可实现自动增长的对象数组,使用Vector作为存储数组
        Vector<Integer> arr;
        arr = new Vector<>();
        //首先将第一位丑数存入到
        arr.add(newNum);
        //遍历访问arr数组
        while(arr.size()<index){
            //找出分别有三个队列产生的最小数
            newNum=minNum(arr.get(p2) *2,minNum(arr.get(p3) *3, arr.get(p5) *5));
            //这三个if有可能进入一个或者多个，进入多个是三个队列头中最小的数有多个的情况
            if(arr.get(p2) *2==newNum){p2++;}
            if(arr.get(p3) *3==newNum){p3++;}
            if(arr.get(p5) *5==newNum){p5++;}
            arr.add(newNum);
        }
        return newNum;
    }
    private static  int minNum(int i,int j){
        if(i>j){
            return j;
        }else{
            return i;
        }
    }
}