题目

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

示例 1：输入：n = 3, a = 2, b = 3, c = 5 输出：4

解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

示例 2：输入：n = 4, a = 2, b = 3, c = 4 输出：6

解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

示例 3：输入：n = 5, a = 2, b = 11, c = 13 输出：10

解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

示例 4：输入：n = 1000000000, a = 2, b = 217983653, c = 336916467 输出：1999999984

提示：1 <= n, a, b, c <= 10^9

1 <= a * b * c <= 10^18

本题结果在 [1, 2 * 10^9] 的范围内

解题思路分析

1、二分查找；时间复杂度O(log(n))，空间复杂度O(1)

func nthUglyNumber(n int, a int, b int, c int) int {
   ab, ac, bc := lcm(a, b), lcm(a, c), lcm(b, c)
   abc := lcm(ab, c)
   left := 1
   right := 2000000000
   for left <= right {
      mid := left + (right-left)/2
      total := mid/a + mid/b + mid/c - mid/ab - mid/ac - mid/bc + mid/abc
      if total == n {
         if mid%a == 0 || mid%b == 0 || mid%c == 0 {
            return mid
         }
         right = mid - 1
      } else if total < n {
         left = mid + 1
      } else {
         right = mid - 1
      }
   }
   return left
}

// 求最小公倍数
func lcm(x, y int) int {
   return x * y / gcd(x, y)
}

// 求最大公约数
func gcd(a, b int) int {
   if a < b {
      a, b = b, a
   }
   if a%b == 0 {
      return b
   }
   return gcd(a%b, b)
}

2、二分查找；时间复杂度O(log(n))，空间复杂度O(1)

func nthUglyNumber(n int, a int, b int, c int) int {
   ab, ac, bc := lcm(a, b), lcm(a, c), lcm(b, c)
   abc := lcm(ab, c)
   left := 0
   right := 2000000000
   for left < right {
      mid := left + (right-left)/2
      total := mid/a + mid/b + mid/c - mid/ab - mid/ac - mid/bc + mid/abc
      if total >= n {
         right = mid
      } else {
         left = mid + 1
      }
   }
   return left
}

// 求最小公倍数
func lcm(x, y int) int {
   return x * y / gcd(x, y)
}

// 求最大公约数
func gcd(a, b int) int {
   if a < b {
      a, b = b, a
   }
   if a%b == 0 {
      return b
   }
   return gcd(a%b, b)
}

总结

Medium题目，丑数系列题目，这里是求第n个丑数，n比较大，使用二分查找