[每日一题] 2748.美丽下标对的数目

博主： Richard
发布时间：2024 年 06 月 20 日
78 次浏览
暂无评论
1288字数
分类： LeetCode

> https://leetcode.cn/problems/number-of-beautiful-pairs/description/?envType=daily-question&envId=2024-05-02

### 暴力法

直接枚举 `nums[i]` 即可。

```c++
class Solution {
public:
    int countBeautifulPairs(std::vector<int>& nums) {
        const int n = nums.size();

int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int first = nums[i], last = nums[j] % 10;
                while (first >= 10)
                    first /= 10;

if (gcd(first, last) == 1)
                    res++;
            }
        }
        
        return res;
    }
};
```

- 时间复杂度：$O(n \times (n + logC))$ ，其中 $n$ 为数组的长度， $C$ 为 `nums[i]` 的最大值。
- 空间复杂度：$O(1)$ 。

### 哈希表

`nums[i]` 的最高位取值范围为 $[1, 9]$ ，所以可以在遍历数组的同时，统计每个数字在最高位出现的次数。这样就只需要判断 $[1, 9]$ 是否和 $x \ mod \ 10$ 互质，如果互质则将对应的出现次数加到答案中即可。

```c++
class Solution {
public:
    int countBeautifulPairs(std::vector<int>& nums) {
        int res = 0, cnt[10]{};
        
        for (int num: nums) {
            for (int i = 1; i <= 9; i++) {
                if (gcd(num % 10, i) == 1) {
                    res += cnt[i];
                }
            }
            while (num >= 10) {
                num /= 10;
            }
            cnt[num]++;
        }
        return res;
    }
};
```

- 时间复杂度：$O(n \times (10 + logC))$ ，其中 $n$ 为数组的长度， $C$ 为 `nums[i]` 的最大值。
- 空间复杂度：$O(1)$ 。

最后修改：2024 年 06 月 20 日