CTF of Z2BNS
0%

好数对的数目

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 911 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

示例1：

1
2
3
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始

示例2：

1
2
3
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对

示例3：

1
2
输入：nums = [1,2,3]
输出：0

限制：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

双for循环遍历

c++代码：(执行用时4ms，击败48.99%，内存消耗7.5M，击败8.81%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int result=0;
        for(int i=0;i<nums.size();++i){
            for(int j=i+1;j<nums.size();++j){
                if(nums[i]==nums[j]){
                    //下面这行改成++result;执行用时为0，击败100%，优秀
                    result+=1;
                }
            }
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解：

方法一：暴力统计
思路与算法

对于每个$a_i$,枚举所有的$a_j(j>i)$，检查是否满足$a_i=a_j$，如果是就计入答案。

代码：（执行0ms，击败100%，内存7.6M，击败5.05%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] == nums[j]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n^2)$。
  • 空间复杂度：$O(1)$。

方法二：组合计数
思路与算法

用哈希表统计每个数在序列中出现的次数，假设数字 $k$ 在序列中出现的次数为 $v$，那么满足题目中所说的 $nums[i]=nums[j]=k(i<j)$ 的 $(i,j)$ 的数量就是$\frac{v(v - 1)}{2} $，即$ k$ 这个数值对答案的贡献是 $\frac{v(v - 1)}{2}$ 。我们只需要把所有数值的贡献相加，即可得到答案。

代码：（执行0ms，击败100%，内存7.6M，击败5.05%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map <int, int> m;
        for (int num: nums) {
            ++m[num];
        }
        int ans = 0;
        for (const auto &[k, v]: m) {
            ans += v * (v - 1) / 2;
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$，即哈希表使用到的辅助空间的空间代价。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

我用的是第一种暴力统计方法，不过变量值加1的写法效率还不同，++ans;要优于ans+=1;😑

------------- THE END! THANKS! -------------