LeetCode每日一题

题目来源：力扣（LeetCode）

2748. 美丽下标对的数目（简单）

暴力枚举 哈希表

题目描述

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 ，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。

返回 nums 中 美丽下标对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 y 的 最大公因数 。

示例 1：

输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 1 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。5 和 1 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。5 和 4 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。1 和 4 互质，因此 gcd(1,4) == 1 。
因此，返回 5 。

示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1 。
因此，返回 2 。

提示：

  • $2 <= nums.length <= 100$
  • $1 <= nums[i] <= 9999$
  • $nums[i] \% 10 != 0$

题解

方法一：暴力枚举
暴力枚举 $nums[i]$ 和 $nums[j]$，判断是否是美丽下标对。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        for i in range(n):
            while nums[i] >= 10:
                nums[i] //= 10  # 取nums[i]的第一个数字
            for j in range(i + 1, n):
                if gcd(nums[i] , nums[j] % 10) == 1:  # 取nums[j]的最后一个数字，并获取其与nums[i]的最大公约数
                    res += 1
        return res

复杂度分析

  • 时间复杂度：$O(n^{2}logC))$，其中 $n$ 是数组 $nums$ 的长度，$C$ 是 $nums$ 中的最大元素。

    • 外层循环 $i$：遍历数组中的每一个元素，有 $n$ 次迭代。

    • 外+内层循环 $j$：对于每个 $i$，内层循环遍历从 $i+1$ 到 $n-1$ 的所有元素，平均执行次数为 $\frac{n(n-1)}{2}$，约等于 $O(n^{2})$。

    • 计算 gcd：最大公约数算法的时间复杂度是 $O(logC)$，因为两个数的最大公约数的计算复杂度与数的大小成对数关系。

    • 综上代码中最耗时的操作是内层的 gcd 计算，需要在 $O(n^{2})$ 次迭代中每次执行 $O(logC)$ 次除法。因此，总的时间复杂度是 $O(n^{2}logC)$。

  • 空间复杂度：$O(1)$。

方法二：哈希表

用一个数组 $cnt[y]$ 来表示当前 第一个数字 为 $y$ 的元素个数。

遍历数组。

  • 求出当前元素的 最后一个数字；
  • 枚举 1 到 9，判断当前元素的 最后一个数字 可以与 1 到 9 哪个数字互质；
    • 根据当前 $cnt$ 中记录的可互质的 第一个数字 的元素个数，更新 美丽下标对 个数 $res$ 。
  • 在移动到下一位置前，根据该位置的 第一个数字 的元素值更新 $cnt$
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        res = 0
        cnt = [0] * 10
        for x in nums:
            for y in range(1, 10):
                if gcd(x % 10, y) == 1:  # 当前最后一个数字可以与哪个数字互质
                    res += cnt[y]  # 利用cnt中当前可互质的元素个数，更新美丽下标对个数res 
            while x >= 10:
                x //= 10
            cnt[x] += 1  # 更新当前第一个数字为x的元素个数
        return res

复杂度分析

  • 时间复杂度：$O(10nlogC))$，其中 $n$ 是数组的长度，$C$ 是 $nums[i]$ 的最大值。

  • 空间复杂度：$O(10)$。