美丽下标对的数目

难度: Easy

给你一个下标从 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 和 k 最大公因数 。

示例 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 和 5 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 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

Submission

运行时间: 69 ms

内存: 16.1 MB

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        ans,cnt =0,[0]*10
        for x in nums:
            for y in range(1,10):
                if cnt[y] and gcd(x%10,y)==1:
                    ans+=cnt[y]
            while x>=10:x//=10
            cnt[x]+=1
        return ans

Explain

题解采用了计数排序和贪心的方法来高效处理美丽下标对的统计。首先，创建了一个大小为10的数组cnt，用来计数每个数字（1到9）作为第一个数字出现的次数。对于nums中的每个元素x，首先判断其最后一个数字（x%10）与已统计的第一个数字是否互质，如果互质，则增加对应的cnt[y]值到结果ans中，这样确保了不重复统计下标对。然后，通过不断除以10将x缩小，直到x小于10，此时x就是该数字的第一个数字，对应的cnt[x]增加1，用于后续的配对统计。

时间复杂度: O(n)

空间复杂度: O(1)

from typing import List
from math import gcd

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        ans = 0  # 美丽下标对的计数
        cnt = [0] * 10  # 数字1-9的计数数组
        for x in nums:  # 遍历nums中的每个数字
            for y in range(1, 10):  # 与1-9每个可能的第一个数字比较
                if cnt[y] and gcd(x % 10, y) == 1:  # 如果当前数字的最后一个数字与y互质
                    ans += cnt[y]  # 增加已计数的配对次数
            while x >= 10:  # 获取当前数字的第一个数字
                x //= 10
            cnt[x] += 1  # 计数当前数字的第一个数字出现的次数
        return ans  # 返回总的美丽下标对数量

Explore

在这个问题中，我们的目标是统计具有特定属性（互质的第一个和最后一个数字）的下标对的数目，而不是对数组元素进行排序。计数排序在这里被用作一种计数技术，而非传统意义上的排序。由于我们只关心数字1到9的出现次数，使用一个固定大小（10）的数组来快速统计和访问这些数字的次数更为高效。这种方法显著减少了时间复杂度，特别是当输入数组很大时，直接计数比全数组排序更优。

这种方法在大多数情况下是有效的，因为它正确地检查了数字x的最后一个数字和数字y是否互质（即gcd为1）。然而，`cnt[y] and gcd(x % 10, y) == 1`首先检查`cnt[y]`是否不为零，即之前是否有数字的第一个数字是y。如果没有，即使x的最后一个数字和y互质，也不会增加计数。这是合理的，因为没有配对的可能。但如果y是0，gcd(0, 0)会是0，gcd(0, y) (y不为0)是y，这种情况下代码应该保证y从1开始，避免0的干扰。

这种处理方式有效地找到了一个大于等于10的数字的第一个数字，通过不断除以10直到数字小于10。如果输入的数字含有0，例如1000，最后得到的第一个数字仍然是1，这是正确的。但需要注意，该方法假设输入的数字都是正整数，如果存在非正整数，这种处理方式可能不适用，因为对于0或负数，该方法没有意义。

循环`for y in range(1, 10)`基于这样一个事实：我们只关心1到9这九个数字作为第一个数字的情况，因为按照题目的设定，这是可能的范围（通常不考虑0作为首位数字，且题目可能已经限定了数字范围）。这确实意味着所有有效的nums元素的第一个数字都应该在1到9之间。如果nums包含如0或负数这样的元素，需要额外的处理来排除或适应这些情况。