转载

丑树

丑树

题目

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

思路

  • 初始化array和队列:Q2 Q3 Q5

  • 将1插入array

  • 分别将1 * 2、1 * 3 、1*5插入Q2 Q3 Q5

  • 令x为Q2 Q3 Q5中的最小值,将x添加至array尾部

  • 若x存在于:

        Q2:将 x * 2、x * 3、x*5 分别放入Q2 Q3 Q5,从Q2中移除x
        Q3:将 x * 3、x*5 分别放入Q3 Q5,从Q3中移除x
        Q5:将 x * 5放入Q5,从Q5中移除x

  • 重复步骤4~6,知道找到第k个元素

Q1队列: 2 2x2 2x2x2 2x2x2 ….

Q2队列:3 2x3 3x3 2x2x3…

Q3队列:5 2x5 3x5 2x2x5 …

代码

import java.util.ArrayList;
import java.util.LinkedList;


public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0) return 0;
        ArrayList<Integer> list = new ArrayList<Integer>();

        LinkedList<Integer> two = new LinkedList<Integer>();
        LinkedList<Integer> three = new LinkedList<Integer>();
        LinkedList<Integer> five = new LinkedList<Integer>();

        list.add(1);
        two.offer(2); three.offer(3); five.offer(5);

        int a = 0, b = 0, c = 0;
        int temp = 0;

        while(list.size() < index) {
            a = two.peek(); b = three.peek(); c = five.peek();
            temp = min(a, b, c);
            list.add(temp);
            if(temp == a) {
                two.poll();
                two.offer(temp * 2);
                three.offer(temp * 3);
                five.offer(temp * 5);
            }

            if(temp == b) {
                three.poll();
                three.offer(temp * 3);
                five.offer(temp * 5);
            }

            if(temp == c) {
                five.poll();
                five.offer(temp * 5);
            }
        }
        return list.get(index - 1);
    }

    public int min(int a, int b, int c) {
        int temp = 0;
        if(a > b) temp = b; else temp = a;

        if(temp > c) return c; else return temp;
    }
}
正文到此结束
本文目录