数据结构02附录02:哈希表[C++]

发布时间:2024年01月10日

图源:文心一言

上机题目练习整理~🥝🥝

本篇作为线性表的代码补充,每道题提供了优解和暴力解算法,供小伙伴们参考~🥝🥝

  • 第1版:在力扣新手村刷题的记录,优解是Bard老师提供的建议~🧩🧩

编辑:梅头脑🌸

题目: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]

  1. 首先,我们将数组中的每个元素插入哈希表?hash?中。这里应该会经过取余运算,即1%6=1,2%6=2,3%6=3。

  1. 然后,我们遍历哈希表?hash
  • 对于元素?1hash[1] = 3,说明元素?1?出现了 3 次。因此,存在 2 个好数对,下标分别为 (0, 3) 和 (0, 4)。
  • 对于元素?2hash[2] = 1,说明元素?2?只出现了一次,因此不存在好数对。
  • 对于元素?3hash[3] = 2,说明元素?3?出现了 2 次。因此,存在 1 个好数对,下标分别为 (2, 5)。
  1. 最后,我们将所有好数对的数目加起来,得到最终结果?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这篇博文有的答案写得不太好,最近正在绞尽脑汁准备修改中——

博文到此结束,写得模糊或者有误之处,欢迎小伙伴留言讨论与批评,督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等,博主会顶锅前来修改~~😶?🌫?😶?🌫?

我是梅头脑,本片博文若有帮助,欢迎小伙伴动动可爱的小手默默给个赞支持一下,感谢点赞小伙伴对于博主的支持~~🌟🌟

数据结构_梅头脑_的博客-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/weixin_42789937/category_12262100.html?spm=1001.2014.3001.5482

文章来源:https://blog.csdn.net/weixin_42789937/article/details/135497096
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。