牛客網——醜數

題目描述
把隻包含質因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含質因子7。 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第N個醜數。
           

我直接用三個隊列做的，分别存放2的倍數，3的倍數，5的倍數

package 劍指offer;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by Administrator on 2018/10/24.
 */
public class 醜數 {
    public static int GetUglyNumber_Solution(int index) {
        Queue<Integer> que1=new LinkedList<>(),
                que2=new LinkedList<>(),
                que3=new LinkedList<>();
        int min=1,num=1;
//        que1.add(1);
        while(num<index){
            if((min*2)%7!=0)
               que1.add(min*2);
            if((min*3)%7!=0&&(min*3)%2!=0)
                que2.add(min*3);
            if((min*5)%7!=0&&(min*5)%2!=0&&(min*5)%3!=0)
                que3.add(min*5);
            int num1=que1.isEmpty()?Integer.MAX_VALUE:que1.peek(),
                    num2=que2.isEmpty()?Integer.MAX_VALUE:que2.peek(),
                    num3=que3.isEmpty()?Integer.MAX_VALUE:que3.peek();
            if(num1<=num2&&num1<=num3){
                min=num1;
                que1.poll();
            }else if(num2<=num1&&num2<=num3){
                min=num2;
                que2.poll();
            }else {
                min=num3;
                que3.poll();
            }
            num++;
        }
        return min;
    }

    @Test
    public void test(){
        System.out.println(GetUglyNumber_Solution(9));
    }
}

           

在讨論區看到的一個機智的做法，思路差不多，但實作好多了

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index < 7)return index;
        vector<int> res(index);
        res[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0, i;
        for (i = 1; i < index; ++i)
        {
            res[i] = min(res[t2] * 2, min(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];
    }
};