剑指Offer——丑数

  

   

    

     

    
    

     

      package cn.edu.ujn.offersword;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import java.util.Scanner;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class C5_34_UglyNumber {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * @date 2016-09-16
     
    
   

    

     

    
    

     

       * @number 01
     
    
   

    

     

    
    

     

       * @author SHQ
     
    
   

    

     

    
    

     

       * 丑数
     
    
   

    

     

    
    

     

       * 题目描述
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       * 思路
     
    
   

    

     

    
    

     

       *空间换时间
     
    
   

    

     

    
    

     

       *根据丑数的定义，丑数应该是另一个丑数乘以2，3，或5所得(1除外)。故非丑数不在计算范围之内。额外创建一个数组，用于存放已确定的丑数。
     
    
   

    

     

    
    

     

       *通过设置3个变量，用于标记第一个大于最大丑数的位置，并将3个变量中的最小丑数作为下一个丑数。 同时避免重复计算。
     
    
   

    

     

    
    

     

       * 空间复杂度O(n);
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public static void main(String[] args) {
     
    
   

    

     

    
    

     

      Scanner in = new Scanner(System.in);
     
    
   

    

     

    
    

     

      while(in.hasNextInt()){
     
    
   

    

     

    
    

     

      int index = in.nextInt();
     
    
   

    

     

    
    

     

      System.out.println(GetUglyNumber_Solution2(index));
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      // 超时
     
    
   

    

     

    
    

     

       private static int GetUglyNumber_Solution(int index) {
     
    
   

    

     

    
    

     

       if(index <= 0){
     
    
   

    

     

    
    

     

       return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       int cnt = 0;
     
    
   

    

     

    
    

     

       int number = 1;
     
    
   

    

     

    
    

     

       while(cnt < index){
     
    
   

    

     

    
    

     

       if(isUgly(number)){
     
    
   

    

     

    
    

     

       cnt++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       number++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       return number;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       
     
    
   

    

     

    
    

     

       private static boolean isUgly(int num){
     
    
   

    

     

    
    

     

       while(num % 2 == 0)
     
    
   

    

     

    
    

     

       num /= 2;
     
    
   

    

     

    
    

     

       while(num % 3 == 0)
     
    
   

    

     

    
    

     

       num /= 3;
     
    
   

    

     

    
    

     

       while(num % 5 == 0)
     
    
   

    

     

    
    

     

       num /= 5;
     
    
   

    

     

    
    

     

       return num == 1 ? true : false;
     
    
   

    

     

    
    

     

       
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       
     
    
   

    

     

    
    

     

       private static int GetUglyNumber_Solution2(int index) {
     
    
   

    

     

    
    

     

       if(index <= 0){
     
    
   

    

     

    
    

     

       return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       int [] arr = new int [index];
     
    
   

    

     

    
    

     

       arr[0] = 1;
     
    
   

    

     

    
    

     

       int index2 = 0, index3 = 0, index5 = 0, nextIndex = 1;
     
    
   

    

     

    
    

     

       while(nextIndex < index){
     
    
   

    

     

    
    

     

       System.out.print(arr[nextIndex-1] + " ");
     
    
   

    

     

    
    

     

       int min = min(arr[index2]*2, arr[index3]*3, arr[index5]*5);
     
    
   

    

     

    
    

     

       arr[nextIndex] = min;
     
    
   

    

     

    
    

     

       while(arr[index2] * 2 <= arr[nextIndex])
     
    
   

    

     

    
    

     

       index2++;
     
    
   

    

     

    
    

     

       while(arr[index3] * 3 <= arr[nextIndex])
     
    
   

    

     

    
    

     

       index3++;
     
    
   

    

     

    
    

     

       while(arr[index5] * 5 <= arr[nextIndex])
     
    
   

    

     

    
    

     

       index5++;
     
    
   

    

     

    
    

     

       nextIndex++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       return arr[nextIndex-1];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       
     
    
   

    

     

    
    

     

       private static int min(int a, int b, int c){
     
    
   

    

     

    
    

     

       int min = (a > b) ? b : a; 
     
    
   

    

     

    
    

     

       return min > c ? c : min;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

美文美图

文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。

原文链接：shq5785.blog.csdn.net/article/details/52556919