题解 | #丑数#

import java.util.*;
public class Solution {
    
    public int GetUglyNumber_Solution1(int index) {
        List<Integer> list1=new ArrayList<Integer>();//存储素数
        List<Integer> list2=new ArrayList<Integer>();//存储丑数
        int i=1;
        while(true){
            getSubNum(i,list1,list2);
            if(list2.size()==index){
                return list2.get(index-1);
            }
            i++;
        }

    }
    public void getSubNum(int num,List<Integer> list1,List<Integer> list2){
        if(num==1){
            list1.add(num);
            list2.add(num);
            return;
        }
        int div_num=num/2;
        Set<Integer> set=new HashSet<Integer>();
        for(int i=1;i<=num;i++){
            int tmp1=num/i;
            int tmp2=num%i;
            if(tmp2==0){
                set.add(tmp1);
                set.add(num/i);
            }
        }
        if(set.size()==2){
            list1.add(num);
        }
        for(int n:list1){
            if(set.contains(n)&&n!=1&&n!=2&&n!=3&&n!=5){
                return;
            }
        }
        list2.add(num);
        
    }
    public int GetUglyNumber_Solution(int index) {
        if(index<=0)return 0;
        int num2=0;
        int num3=0;
        int num5=0;
        List<Integer> list=new ArrayList<Integer>();
        list.add(0,1);
        //头插法,第一个元素即为方法目标对象
        for(int i=1;i<index;i++){
            int min_num=Math.min(2*list.get(num2),Math.min(3*list.get(num3),5*list.get(num5)));
            list.add(min_num);
            if(min_num==2*list.get(num2))num2++;
            if(min_num==3*list.get(num3))num3++;
            if(min_num==5*list.get(num5))num5++;
            
        }
        return list.get(index-1);
    }
}