【剑指offer-Java版】34丑数

素颜马尾好姑娘i 2022-08-21 09:48 135阅读 0赞

丑数:返回第N个丑数

只包含因子 2 3 5的数称为丑数，第一个丑数是 1

采用辅助数组的方法，提高时间效率 – 下一个丑数一定是已有的丑数乘以2 或者 3 或者 5 得到的

public class _Q34<T> {
    
    
        public int GetUglyNumber(int count){
    
            if(count < 1) return 0;
            if(count == 1) return 1;
    
            int uglyArray[] = new int[count];
            uglyArray[0] = 1; // 第一个丑数是 1
    
            int nextUglyIndex = 1;
            int nextUglyNum = 0;
    
            int index2 = 0; // 记录第一个满足uglyArray[]*2 > 当前最大丑数 的下标
            int index3 = 0;
            int index5 = 0;
    
            while(nextUglyIndex < count){
                nextUglyNum = MinInThree((uglyArray[index2]*2), (uglyArray[index3]*3), (uglyArray[index5]*5));
    
                uglyArray[nextUglyIndex] = nextUglyNum;
    
                while(uglyArray[index2]*2 <= uglyArray[nextUglyIndex]){
                    index2++;
                }
    
                while(uglyArray[index3]*3 <= uglyArray[nextUglyIndex]){
                    index3++;
                }
    
                while(uglyArray[index5]*5 <= uglyArray[nextUglyIndex]){
                    index5++;
                }
    
                nextUglyIndex++;
            }
    
    
            return uglyArray[nextUglyIndex-1];
        }
    
        private int MinInThree(int num1, int num2, int num3){
            //return (num1 < num2 ? num1:num2) < num3 ? (num1 < num2 ? num1:num2) : num3;
            int min = num1 < num2 ? num1 : num2;
            min = min < num3 ? min : num3;
            return min;
        }
        }

测试代码：

public class _Q34Test extends TestCase {
    
        _Q34 ugly = new _Q34();
    
        public void test(){
            System.out.println(ugly.GetUglyNumber(1));
            System.out.println(ugly.GetUglyNumber(2));
            System.out.println(ugly.GetUglyNumber(3));
            System.out.println(ugly.GetUglyNumber(4));
            System.out.println(ugly.GetUglyNumber(5));
            System.out.println(ugly.GetUglyNumber(6));
            System.out.println(ugly.GetUglyNumber(7));
            System.out.println(ugly.GetUglyNumber(8));
            System.out.println(ugly.GetUglyNumber(9));
            System.out.println(ugly.GetUglyNumber(10));
            System.out.println(ugly.GetUglyNumber(11));
    
            System.out.println(ugly.GetUglyNumber(0));
            System.out.println(ugly.GetUglyNumber(1500));
        }
        }