264. Ugly Number II.md

264. Ugly Number II

---

leetcode Daily Challenge on July 4th, 2020.

---

Difficulty : Medium

Related Topics : Math、Dynamic Programming、Heap

---

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

• 1 is typically treated as an ugly number.
• n does not exceed 1690.

---

Solution

• mine
  • Java
    • Runtime: 129 ms, faster than 10.85%, Memory Usage: 39 MB, less than 39.87% of Java online submissions

      // O(N^2)time
      // O(N)space
      public int nthUglyNumber(int n) {
          int[] mul = new int[]{2, 3, 5};
          List<Integer> list = new ArrayList<>(n);
          list.add(1);
          while(n > 1){
              n--;
              int size = list.size();
              int max = list.get(list.size() - 1);
              long res = Integer.MAX_VALUE;
              for(int i = 0; i < size; i++){
                  for(int j = 0; j < 3; j++){
                      long t = (long) mul[j] * list.get(i);
                      if(t > max){
                          res = Math.min(res, t);
                          if(j == 0){
                              break;
                          }
                      }
                  }
              }
              list.add((int)res);
              int i = 0;
              while(list.get(i) * mul[2] < list.get(size)){
                  i++;
              }
              while(i > 0){
                  list.remove(0);
                  i--;
              }
          }
          return list.get(list.size() - 1);
      }
      

---

• the most votes

• Runtime: 2 ms, faster than 97.49%, Memory Usage: 37.4 MB, less than 78.59% of Java online submissions

  // O(N)time
  // O(N)space
  public int nthUglyNumber(int n) {
      int[] ugly = new int[n];
      ugly[0] = 1;
      int index2 = 0, index3 = 0, index5 = 0;
      int factor2 = 2, factor3 = 3, factor5 = 5;
      for(int i=1;i<n;i++){
          int min = Math.min(Math.min(factor2,factor3),factor5);
          ugly[i] = min;
          if(factor2 == min)
              factor2 = 2*ugly[++index2];
          if(factor3 == min)
              factor3 = 3*ugly[++index3];
          if(factor5 == min)
              factor5 = 5*ugly[++index5];
      }
      return ugly[n-1];
  }
  

---