LeetCode每日一题

题目来源:力扣(LeetCode)

2748. 美丽下标对的数目(简单)

暴力枚举 哈希表

题目描述

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

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

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

示例 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)$。