当前位置：首页 > article >正文

2748. 美丽下标对的数目（Beautiful Pairs）

article 2025/1/31 1:21:45

2748. 美丽下标对的数目（Beautiful Pairs）

题目分析

给定一个整数数组 nums，我们需要找出其中符合条件的“美丽下标对”。美丽下标对是指，数组中的某一对数字 nums[i] 和 nums[j]（其中 0 ≤ i < j < nums.length）满足以下条件：

nums[i] 的第一个数字（即 nums[i] 的最左边的数字）
nums[j] 的最后一个数字（即 nums[j] 的最右边的数字）

这两个数字互质，即 gcd(nums[i]的第一个数字, nums[j]的最后一个数字) == 1。如果满足这个条件，则认为这对下标是“美丽下标对”。

题解思路

暴力解法

在这个问题中，最简单的做法是使用双重循环来遍历所有可能的数字对，然后判断它们的第一个数字和最后一个数字是否互质。

步骤分析：

提取数字的第一个数字和最后一个数字：
- 对于 nums[i]，我们可以通过字符串操作或者数学运算得到其第一个数字。
- 对于 nums[j]，我们可以直接用 nums[j] % 10 来获取最后一个数字。
计算 gcd：
- 使用 Python 中的 math.gcd 函数来计算两个数字的最大公约数。
- 如果 gcd 的结果是 1，则认为这对数字互质。
统计美丽下标对：
- 对于每一对 (i, j)，如果它们满足互质的条件，增加计数器。

代码实现

Python 代码

from math import gcd

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        n, res = len(nums), 0
        for i in range(n):
            for j in range(i + 1, n):
                # 提取第一个数字和最后一个数字
                a = int(str(nums[i])[0])  # nums[i] 的第一个数字
                b = nums[j] % 10  # nums[j] 的最后一个数字
                # 判断是否互质
                if gcd(a, b) == 1:
                    res += 1
        return res

C++ 代码

#include <vector>
#include <numeric>  // gcd
using namespace std;

class Solution {
public:
    int countBeautifulPairs(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                int a = nums[i], b = nums[j] % 10;
                // 提取 nums[i] 的第一个数字
                while (a >= 10) {
                    a /= 10;
                }
                // 判断是否互质
                if (gcd(a, b) == 1) {
                    res++;
                }
            }
        }
        return res;
    }
};

代码优化与分析

暴力解法的时间复杂度：
- 外层循环遍历所有的 i，内层循环遍历所有的 j，因此总共有 O(n^2) 次操作。对于 n <= 100（题目限制），这样的时间复杂度是可以接受的。
- 提取数字的第一个数字和最后一个数字的操作是常数时间 O(1)，所以整体时间复杂度为 O(n^2)。
优化点：
- 暴力解法已经是最直观的解决方案，但由于题目中数组的长度最大为 100，在这个范围内时间复杂度 O(n^2) 是能够承受的。因此，当前的暴力解法对于本题来说足够高效。
- 如果数据规模更大，可能需要考虑其他优化方法，比如使用哈希表等数据结构来减少重复计算，但在这里并不需要。