图源:文心一言
上机题目练习整理~🥝🥝
本篇作为线性表的代码补充,每道题提供了优解和暴力解算法,供小伙伴们参考~🥝🥝
编辑:梅头脑🌸
题目:1512. 好数对的数目 - 力扣(LeetCode)
给你一个整数数组?
nums
?。如果一组数字?
(i,j)
?满足?nums[i]
?==?nums[j]
?且?i
?<?j
?,就可以认为这是一组?好数对?。返回好数对的数目。
示例 1:
输入:nums = [1,2,3,1,1,3] 输出:4 解释:有 4 组好数对,分别是 (0,3), (0,4), (3,4), (2,5) ,下标从 0 开始示例 2:
输入:nums = [1,1,1,1] 输出:6 解释:数组中的每组数字都是好数对示例 3:
输入:nums = [1,2,3] 输出:0
📇优解思路
- 算法思想:
- 使用哈希表?
hash
?存储元素出现的次数。- 遍历哈希表,统计每个元素出现的次数大于 1 的情况。
- 对于每个出现的次数大于 1 的元素,其好数对的数目为?
出现的次数 - 1
。- 时间复杂度:O(n),其中n是数组的长度,因为遍历1遍数组。
- 空间复杂度:O(n),其中n是数组的长度,因为哈希表占用的长度为n。
???优解代码
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int count = 0;
unordered_map<int, int> hash; // 声明一个哈希表 hash,键为 int 型,值为 int 型
for (int num : nums) { // 遍历数组 nums 中的每个元素 num
hash[num]++; // 将元素 num 在哈希表 hash 中出现的次数加 1
if (hash[num] > 1) { // 如果元素 num 出现的次数大于 1,则说明存在好数对
count += hash[num] - 1; // 将好数对的数目加 hash[num] - 1
}
}
return count;
}
};
???哈希表解释
哈希表简介
哈希表是一种以键值对存储数据的抽象数据结构。它利用哈希函数将键映射到一个索引,从而快速查找键值对。
哈希表的基本操作
- 插入:将键值对插入哈希表。
- 查找:根据键查找哈希表中的值。
- 删除:根据键删除哈希表中的键值对。
哈希表的特点
- 查找速度快:哈希表的平均查找时间复杂度为 O(1)。
- 空间利用率高:哈希表可以有效利用空间,减少内存浪费。
- 哈希冲突:当不同的键映射到同一个索引时,就会发生哈希冲突。
哈希表的详细介绍,可以参考 大佬?嗯行家啊 的博文:
🌸一文看懂哈希表并学会使用C++ STL 中的哈希表_哈希表end函数-CSDN博客
???代码运行
假设数组
nums
为[1, 2, 3, 1, 1, 3]
。
- 首先,我们将数组中的每个元素插入哈希表?
hash
?中。这里应该会经过取余运算,即1%6=1,2%6=2,3%6=3。
- 然后,我们遍历哈希表?
hash
。
- 对于元素?
1
,hash[1] = 3
,说明元素?1
?出现了 3 次。因此,存在 2 个好数对,下标分别为 (0, 3) 和 (0, 4)。- 对于元素?
2
,hash[2] = 1
,说明元素?2
?只出现了一次,因此不存在好数对。- 对于元素?
3
,hash[3] = 2
,说明元素?3
?出现了 2 次。因此,存在 1 个好数对,下标分别为 (2, 5)。
- 最后,我们将所有好数对的数目加起来,得到最终结果?
4
。
📇暴力解思路
- 算法思想:
- 2层for循环,外层为数组下标 i 的循环,内层为数组下标 j 的循环;
- 当nums[i] == nums[j]时,增加好数对的记录;
- 时间复杂度:O(n2),因为使用了2层循环。
- 空间复杂度:O(1),只有count占用了位置。
??暴力解代码
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int length = nums.size();
int count = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (nums[i] == nums[j])
count++;
}
}
return count;
}
};
2013年有一道题目的暴力解也可以用哈希表,因为格式粘过来总是有问题,所以干脆发原文链接:🌸数据结构02附录01:顺序表考研习题[C++]-CSDN博客~🥝🥝
不过,附录01这篇博文有的答案写得不太好,最近正在绞尽脑汁准备修改中——
博文到此结束,写得模糊或者有误之处,欢迎小伙伴留言讨论与批评,督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等,博主会顶锅前来修改~~😶?🌫?😶?🌫?
我是梅头脑,本片博文若有帮助,欢迎小伙伴动动可爱的小手默默给个赞支持一下,感谢点赞小伙伴对于博主的支持~~🌟🌟