LeetCode 1201. 丑数 III

Categories:

题目描述
思路分析
1. 解法一：二分查找（推荐）
相似题目

题目描述

✅ 1201. 丑数 III

思路分析

解法一：二分查找（推荐）

核心思路：

二分答案 x，统计 <= x 的可整除数数量。

使用容斥原理：cnt = x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c)。

若计数 >= n，说明答案不大于 x。

复杂度分析：

时间复杂度：O(log M)，其中 M 表示搜索上界。

空间复杂度：O(1)。

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        long left = 1;
        long right = (long) 2e9;

        long ab = lcm(a, b);
        long ac = lcm(a, c);
        long bc = lcm(b, c);
        long abc = lcm(a, (int) bc);

        while (left < right) {
            long mid = left + (right - left) / 2;
            long cnt = mid / a + mid / b + mid / c
                    - mid / ab - mid / ac - mid / bc
                    + mid / abc;

            if (cnt >= n) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return (int) left;
    }

    private long gcd(long x, long y) {
        while (y != 0) {
            long t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    private long lcm(long x, long y) {
        return x / gcd(x, y) * y;
    }
}

func nthUglyNumber(n int, a int, b int, c int) int {
	left := int64(1)
	right := int64(2_000_000_000)

	ab := lcm(int64(a), int64(b))
	ac := lcm(int64(a), int64(c))
	bc := lcm(int64(b), int64(c))
	abc := lcm(int64(a), bc)

	for left < right {
		mid := left + (right-left)/2
		cnt := mid/int64(a) + mid/int64(b) + mid/int64(c) - mid/ab - mid/ac - mid/bc + mid/abc

		if cnt >= int64(n) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return int(left)
}

func gcd(a int64, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func lcm(a int64, b int64) int64 {
	return a / gcd(a, b) * b
}

相似题目

题目	难度	考察点
1201. 丑数 III	困难	二分、容斥
264. 丑数 II	中等	DP
313. 超级丑数	中等	DP
69. x 的平方根	简单	二分
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/72740829