剑指 Offer 49. 丑数

剑指 Offer 49. 丑数

用集合运行速度有点慢啊阿啊

class Solution {
    public int nthUglyNumber(int n) {
        if(n == 1) return 1;
        int index1 = 0;
        int index2 = 0;
        int index3 = 0;
        List<Integer> array = new ArrayList<>();
        array.add(1);
        while(array.size() <= n) {
            int min = Math.min(2*array.get(index1), Math.min(3*array.get(index2), 5*array.get(index3)));
            if(min != array.get(array.size()-1)) {
                    array.add(min);
            }
            if(min == 2*array.get(index1)) {
                index1++;
            } else if(min == 3*array.get(index2)) {
                index2++;
            } else {
                index3++;
            }
        
        }
        return array.get(n-1);

    }
}

这里可以改成数组，并且相同的两个可以一起++
以后比赛只能用数组来做

 public int nthUglyNumber(int n) {
        if(n <=3) return n;
        int index1 = 0;
        int index2 = 0;
        int index3 = 0;
        int[] array = new int[n+1];
        array[0] = 1;
        int p = 1;
        int re1= 2;
        int re2=3;
        int re3=4;
         int min = Integer.MAX_VALUE;
        while(p <= n) {
            re1 =  2*array[index1];
            re2 =  3*array[index2];
            re3 =  5*array[index3];
            min = Math.min(re1, Math.min(re2, re3));
            if(min == re1) {
                index1++;
            }
            if(min == re2) {
                index2++;
            } 
            if(min == re3) {
                index3++;
            }
            array[p++] = min; 
        }
        return array[n-1];
    }