丑数

public int GetUglyNumber_Solution (int index) {
    // write code here
    if(index<=6){
        return index;
    }
    int x=0 ,y=0 ,z=0;
    int[] res=new int[index];
    res[0]=1;
    for(int i=1;i<index;i++){
        // 1做初始化，后续按×2 3 5取最小值，命中的数角标+1
        res[i]=Math.min(res[x]*2 ,Math.min(res[y]*3 ,res[z]*5));
        if(res[i]==res[x]*2){
            x++;
        }
        if(res[i]==res[y]*3){
            y++;
        }
        if(res[i]==res[z]*5){
            z++;
        }
    }
    return res[index-1];
}

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index == 0) return 0;
        int[] prime = {2,3,5};
        PriorityQueue<Long> q = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        
        
        long num = 1l;
        q.offer(num);
        while(index -- > 0) {
            num = q.poll();
            for(int p : prime) {
                if(!set.contains(p * num)) {
                    set.add(p * num);
                    q.offer(p * num);
                }
            }
        }
        return (int)num;
    }
}

import java.util.*;
public class Solution {
    
    public int GetUglyNumber_Solution(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);
        
    }
}

import java.util.*;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 6) {
            return index;
        }
        HashSet<Long> set = new HashSet<>();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        long res = 0;
        int[] BASES = {2, 3, 5};
        set.add(1L);
        pq.offer(1L);
        for (int i = 0; i < index; i++) {
            res = pq.poll();
            for (int j = 0; j < BASES.length; j++) {
                long num = res * BASES[j];
                if (!set.contains(num)) {
                    set.add(num);
                    pq.offer(num);
                }
            }
        }
        return (int)res;
    }
}

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        // 三指针：
        
        // 边界值
        if(index==0){
            return 0;
        }
        // 定义数组
        int arr[] = new int[index];
        // 分别记录x2 x3 x5的索引位置
        int i2=0;
        int i3=0;
        int i5=0;
        // 规定第一个为1；
        arr[0]=1;
        // 每轮循环产生一个丑数
        for(int i=1;i<index;i++){
            arr[i] = Math.min(arr[i2]*2, Math.min(arr[i3]*3,arr[i5]*5));
            
            // 哪个索引对应值被选中成为下一个丑数，哪个索引就+1
            if(arr[i]==arr[i2]*2)
                i2++;
            if(arr[i]==arr[i3]*3)
                i3++;
            if(arr[i]==arr[i5]*5)
                i5++;
        }
        
        return arr[index-1];
    }
}

import java.util.*;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index == 0){
            return 0;
        }
        ArrayList<Integer> list = new ArrayList<>();
        int i2 = 0, i3 = 0, i5 = 0;
        list.add(1);
        for (int i = 1; i < index; i++){
            list.add(Math.min(list.get(i2)*2, Math.min(list.get(i3)*3, list.get(i5)*5)));
            if (list.get(i) == list.get(i2)*2)
                i2++;
            if (list.get(i) == list.get(i3)*3)
                i3++;
            if (list.get(i) == list.get(i5)*5)
                i5++;
        }
        return list.get(index-1);
    }
}

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        
        int[] arr = new int[index];
        arr[0] = 1;
        
        int loc2 = 0;
        int loc3 = 0;
        int loc5 = 0;
        int cur;
        for(int i =1;i<index;++i){
            cur = arr[i-1];
            while(arr[loc2]*2<=cur) loc2++;
            while(arr[loc3]*3<=cur) loc3++;
            while(arr[loc5]*5<=cur) loc5++;
            arr[i] = Math.min(Math.min(arr[loc2]*2,arr[loc3]*3),arr[loc5]*5);
        }
        return arr[index-1];
    }
}

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index==0)return 0;
        int[] res=new int[index];
        int t2=0,t3=0,t5=0;
        res[0]=1;
        for(int i=1;i<index;i++){
           res[i]=Math.min(Math.min(res[t2]*2,res[t3]*3),res[t5]*5);
           if(res[i]==res[t2]*2) t2++;
           if(res[i]==res[t3]*3) t3++;
           if(res[i]==res[t5]*5) t5++;
         }
         return res[index-1];
    }
}

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index==0) return 0;
        int i2=0,i3=0,i5=0;
        int x2,x3,x5;
        int []dp=new int[index];
        dp[0]=1;
        for(int i=1;i<index;i++){
            x2=dp[i2]*2;
            x3=dp[i3]*3;
            x5=dp[i5]*5;//在上一次的基础上累乘
            dp[i]=Math.min(x2,Math.min(x3,x5));//最小值为下一个丑数
            if(dp[i]==x2) i2++;
            if(dp[i]==x3) i3++;
            if(dp[i]==x5) i5++;
        }
        return dp[index-1];
    }
}

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 1) {
            return index;
        }
        int a = 1,
            b = 1,
            c = 1;
        int[] dp = new int[index + 1];
        dp[1] = 1;
        for (int i = 2; i <= index; i++) {
            int n1 = dp[a] * 2,
                n2 = dp[b] * 3,
                n3 = dp[c] * 5;
            dp[i] = Math.min(n1, Math.min(n2, n3));
            if (dp[i] == n1) {
                a++;
            }
            if (dp[i] == n2) {
                b++;
            }
            if (dp[i] == n3) {
                c++;
            }
        }
        return dp[index];
    }
}

import java.lang.*;

//思路：一个丑数成以2/3/5，得到的还是一个丑数；有3个对列pos2/pos3/pos5，每次都取最小的数，放到数组中【小于7的数都是丑数】。
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        //小于7的数都是丑数
        if(index < 7){
            return index;
        }
        
        int[] result = new int[index];
        //1是第一个丑数
        result[0] = 1;
        
        //有3个对列pos2/pos3/pos5，每次都取最小的数，放到数组中
        int pos2=0,pos3=0,pos5=0;
        
        //因为1已经是第一个丑数了,所以这里i从1开始
        for(int i=1;i<index;i++){
            
            
            int a = result[pos2] * 2;
            int b = result[pos3] * 3;
            int c = result[pos5] * 5;
            //实现Math.min(a,b,c)的效果
            result[i] = Math.min(a,Math.min(b,c));
            
            if(result[i] == a){//为了防止重复需要三个if都能够走到
                pos2++;
            }
            
            if(result[i] == b){//为了防止重复需要三个if都能够走到
                pos3++;
            }
            if(result[i] == c){//为了防止重复需要三个if都能够走到
                pos5++;
            }
        }
        
        return result[index-1];
    }
}

使用数组记录，依次添加下一个丑数进数组；
下一个丑数计算：用base2、base3、base5记录三个基数的数组下标，ugly2、ugly3、ugly5分别表示对应基数x2、x3、x5的结果（候选丑数），下一个丑数一定是比当前最后一个丑数大的，所以如果ugly2、ugly3、ugly5如果小于等于当前最后一个丑数，需先移动下标位置重新计算，预处理后下一个丑数即ugly2、ugly3、ugly5三个候选值中的最小值

public static int GetUglyNumber_Solution(int index){
        if(index<=1){
            return index;
        }
        int[] array = new int[index];
        array[0]=1;
        int lastI=1;
        int base2=0,base3=0,base5=0;
        int ugly2=array[base2]*2,ugly3=array[base3]*3,ugly5=array[base5]*5;
        while (lastI<index){
            int max = array[lastI-1];
            while (ugly2<=max){
                base2++;
                ugly2=array[base2]*2;
            }
            while (ugly3<=max){
                base3++;
                ugly3=array[base3]*3;
            }
            while (ugly5<=max){
                base5++;
                ugly5=array[base5]*5;
            }
            array[lastI]=getMin(ugly2,ugly3,ugly5);
            System.out.println("lastI="+lastI+",ugly="+ugly2+","+ugly3+","+ugly5+"==>"+array[lastI]);
            lastI++;
        }
        return array[index-1];
    }
    public static int getMin(int a,int b,int c){
        int min=a;
        if(min>b){
            min=b;
        }
        if(min>c){
            min=c;
        }
        return min;
    }

/*
i>1，第i个丑数必定可分解为2*a或3*b或5*c的形式，必定是由2*a或3*b或5*c而来。
而a，b，c也是i前面的丑数。a前面的丑数，必定已经乘过2得到过丑数。

*/
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 0) {
            return 0;
        }
        int[] u = new int[index];
        u[0] = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i=1;i<index;i++) {
            u[i] = Math.min(u[p2]*2, Math.min(u[p3]*3, u[p5]*5));
            if (u[i] == u[p2]*2) {
                p2++;
            } 
            if (u[i] == u[p3]*3) {
                p3++;
            } 
            if (u[i] == u[p5]*5){
                p5++;
            }
        }
        return u[index-1];
    }
}

看了三个答案，总结一下。。。

**
**

首先从丑数的定义我们知道，一个丑数的因子只有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个丑数，这样的方法得到的丑数也是无序的。那么我们可以维护三个队列：**

（1）丑数数组： 1

乘以2的队列：2

乘以3的队列：3

乘以5的队列：5

选择三个队列头最小的数2加入丑数数组，同时将该最小的数乘以**2,3,5放入三个队列；**

（2）丑数数组：1,2

乘以2的队列：4

乘以3的队列：3，6

乘以5的队列：5，10

选择三个队列头最小的数3加入丑数数组，同时将该最小的数乘以**2,3,5放入三个队列；**

（3）丑数数组：1,2,3

乘以2的队列：4,6

乘以3的队列：6,9

乘以5的队列：5,10,15

选择三个队列头里最小的数4加入丑数数组，同时将该最小的数乘以**2,3,5放入三个队列；**

（4）丑数数组：1,2,3,4

乘以2的队列：6，8

乘以3的队列：6,9,12

乘以5的队列：5,10,15,20

选择三个队列头里最小的数5加入丑数数组，同时将该最小的数乘以**2,3,5放入三个队列；**

（5）丑数数组：1,2,3,4,5

乘以2的队列：6,8,10，

乘以3的队列：6,9,12,15

乘以5的队列：10,15,20,25

选择三个队列头里最小的数6加入丑数数组，但我们发现，有两个队列头都为6，所以我们弹出两个队列头，同时将12,18,30放入三个队列；

……………………

疑问：

1.为什么分三个队列？

丑数数组里的数一定是有序的，因为我们是从丑数数组里的数乘以2,3,5选出的最小数，一定比以前未乘以2,3,5大，同时对于三个队列内部，按先后顺序乘以2,3,5分别放入，所以同一个队列内部也是有序的；

2.为什么比较三个队列头部最小的数放入丑数数组？

因为三个队列是有序的，所以取出三个头中最小的，等同于找到了三个队列所有数中最小的。

实现思路：

我们没有必要维护三个队列，只需要记录三个指针显示到达哪一步；“|”表示指针,arr表示丑数数组；

（1）1

|2

|3

|5

目前指针指向0,0,0，队列头arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5

（2）1 2

2 |4

|3 6

|5 10

目前指针指向1,0,0，队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5

（3）1 2 3

2| 4 6

3 |6 9

|5 10 15

目前指针指向1,1,0，队列头arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5

 public int GetUglyNumber_Solution(int n)     {         if(n0)return 0;         ArrayListInteger> list=new ArrayListInteger>();         list.add(1);         int i2=0,i3=0,i5=0;         while(list.size()n)//循环的条件         {             int m2=list.get(i2)*2;             int m3=list.get(i3)*3;             int m5=list.get(i5)*5;             int min=Math.min(m2,Math.min(m3,m5));             list.add(min);             if(min==m2)i2++;             if(min==m3)i3++;             if(min==m5)i5++;         }         return list.get(list.size()-1);     }

所有的丑数分为三种类型 2i,3i,5*i 其中 i是数组中的元素，一开始只有1

2*1 31 51

22 *31* 51 *22* 32 51 23 32 5*1 2*3 32 52 2*4 33 52 25 *33* 52 *25* 34 52 2*6 34 53 28 *35* 53 *28* 36 54