牛客网——丑数

蔚落 2022-05-03 02:28 129阅读 0赞

题目描述
    把只包含质因子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];
        }
    };