题目描述
给你一个下标从 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
最大公因数 。
样例
输入: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[1] 的最后一个数字是 1。2 和 5 互质,
因此 gcd(2,1) == 1。
i = 1 和 j = 2:nums[0] 的第一个数字是 5,nums[1] 的最后一个数字是 1。2 和 5 互质,
因此 gcd(5,1) == 1。
i = 1 和 j = 3:nums[0] 的第一个数字是 5,nums[1] 的最后一个数字是 4。2 和 5 互质,
因此 gcd(5,4) == 1。
i = 2 和 j = 3:nums[0] 的第一个数字是 1,nums[1] 的最后一个数字是 4。2 和 5 互质,
因此 gcd(1,4) == 1。
因此,返回 5。
输入: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
算法
(哈希表) $O(d^2 \log d + nd)$
- 预处理任意两个数字是否互质。
- 按顺序遍历每个数字,遍历过程中,记录下当前每个最高位数字出现的次数。
- 对于当前元素,取出其最低位数字,并找到与该数字互质的所有数字,累加次数。最后更新最高位数字的出现次数。
时间复杂度
- 预处理的时间复杂度为 $O(d^2 \log d)$,其中 $d$ 为进制的大小。
- 遍历数组累计答案的时间复杂度为 $O(nd)$。
- 故总时间复杂度为 $O(d^2 \log d + nd)$。
空间复杂度
- 需要 $O(d^2)$ 的额外空间存储每个数字的出现次数以及预处理的数组。
C++ 代码
class Solution {
public:
int countBeautifulPairs(vector<int>& nums) {
const int n = nums.size();
int c[10];
memset(c, 0, sizeof(c));
bool v[10][10];
memset(v, 0, sizeof(v));
for (int i = 1; i < 10; i++)
for (int j = i; j < 10; j++)
if (gcd(i, j) == 1)
v[i][j] = v[j][i] = true;
int ans = 0;
for (int x : nums) {
int r = x % 10;
for (int i = 1; i < 10; i++)
if (v[i][r])
ans += c[i];
while (x >= 10)
x /= 10;
++c[x];
}
return ans;
}
};