Day15 347前k个高频元素 栈与队列总结 二叉树理论基础

2023-12-21 20:31:49

347 前k个高频元素

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

  • 输入: nums = [1,1,1,2,2,3], k = 2
  • 输出: [1,2]

示例 2:

  • 输入: nums = [1], k = 1
  • 输出: [1]

? ? ? ? ?本题看到了出现频率、数组,就能想到之前用哈希表map来做的那道题,所以马上盯上哈希表这种方法。首先遍历元素创建一个哈希表,因为此时不知道怎么对哈希表排序,所以又创建了一个容器来装哈希表的value,也就是出现的频率,之后对这个容器进行降序排序,其中用到了greater<int>(),之后遍历k次,每次都让哈去除哈希表里的value和所创建容器的value对比,如果一样并且之前又创建的solu容器没有存放这个结果,那么就将他放入solu中,时间复杂度为两次for循环导致的nk,代码如下:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 定义一个元素和元素数量的哈希表
        vector<int> result; // 存放元素数量的容器
        for(int i = 0; i < nums.size(); i++)
            hash[nums[i]]++;
        for(auto i : hash)
            result.push_back(i.second);
        sort(result.begin(), result.end(), greater<int>()); //将元素数量排序
        vector<int> solu;
        for(int i = 0; i < k; i++)
        {
            for(auto it = hash.begin(); it != hash.end(); it++)
            {
                if(it->second == result[i] && find(solu.begin(),solu.end(),it->first) == solu.end())
                {
                    solu.push_back(it->first);
                    break;
                }
            }
        }
        return solu;
    }
};

? ? ? ? 之后我发现这段代码可能过于繁琐,就去网上找了一下优化这个代码的方法:前面创建哈希表的部分不变,这时候再创建一个容器vector<pair<int,int>>sortedHash来继承哈希表的元素,但是这个容器由于是个vector,所以是可以通过sort来排序的,在最后一个元素写入一个lambda函数用来让他根据value降序,之后遍历这个sortedHash,直到取到k个结果,完整代码如下:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 定义一个元素和元素数量的哈希表
        vector<int> result; // 存放元素数量的容器
        for(int i = 0; i < nums.size(); i++)
            hash[nums[i]]++;
        vector<pair<int, int>> sortedHash(hash.begin(), hash.end());
        sort(sortedHash.begin(), sortedHash.end(), [](const auto& a, const auto& b) {
        return a.second > b.second;
        });

        vector<int> solu;

        for (const auto& pair : sortedHash) 
        {
            if (solu.size() < k) 
            {
                solu.push_back(pair.first);
            } 
            else break;
        }
        return solu;
    }
};

? ? ? ? 但是这个时间复杂度依旧很高,这里采用代码随想录里的方法,优先级队列。缺省情况下priority_queue利用大顶堆完成对元素的排序,这个大顶堆是以vector为表现形式的完全二叉树。因为我们只需要维护前k个元素,所以没有必要用sort里的快速排序,为什么不用大顶堆呢,因为加入元素以后肯定是要pop的,如果用大顶堆,那么pop的就是最大的元素,而我们就要的就是大的,所以本题采用小顶堆,每次将最小的元素弹出,最后小顶堆里积累的就是前k个最大元素。

? ? ? ? 前面遍历创建map没有任何区别,此时创建一个小顶堆priority_queue,这里面有三个参数,一个是队列中元素类型,一个是底层容器的类型,一个是准则。这里尤其不要忘记第二个参数,第三个参数本题采用一个类的形式出现。之后遍历map,每次都将小顶堆里的元素插入进去,一旦超过k了,就将多的那个pop掉。之后再倒序将元素插入到result中,时间复杂度为nlogk,代码如下:

class Solution {
public:
    class mycomparision{
    public:
        bool operator()(const pair<int,int>& a, const pair<int,int>& b)
            {return a.second > b.second;}
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for(auto i : nums)
            map[i]++;
        priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparision> pri_que;
        for(auto it = map.begin(); it != map.end(); it++)
        {
            pri_que.push(*it);
            if(pri_que.size() > k)
            {
                pri_que.pop();
            }
        }
        vector<int> result(k);
        for(int i = k-1; i >=0; i--)
        {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

?栈与队列总结:

????????

在栈与队列系列中,我们强调栈与队列的基础,也是很多同学容易忽视的点。

使用抽象程度越高的语言,越容易忽视其底层实现,而C++相对来说是比较接近底层的语言。

我们用栈实现队列,用队列实现栈来掌握的栈与队列的基本操作。

接着,通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用,以及使用技巧。

通过求滑动窗口最大值,以及前K个高频元素介绍了两种队列:单调队列和优先级队列,这是特殊场景解决问题的利器,是一定要掌握的。

二叉树理论基础:?

? ? ? ? 解题中二叉树一般有两种主要的形式:满二叉树和完全二叉树。

? ? ? ? 同时还有二叉搜索树,这是一个有数值的树,如果它的左子树不为空,则左子树上所有的节点数值均小于根节点的值,如果右子树不为空,则右子树上所有结点的值均大于根节点的值。它的做右子树也分别为二叉排序树。如果左右两个子树高度差的绝对值不超过1,那么就成为平衡二叉搜索树,也叫ALV树。cpp中的set ,map, multimap,multiset的底层实现都是ALV树,增删操作时间复杂度为logn,而unordered系列底层实现为哈希表。

? ? ? ? 二叉树有顺序存储和链式存储两种方式,如果顺序存储用数组就可以表示。

? ? ? ? 二叉树有两种遍历方式:

? ? ? ? 1、深度优先遍历:先往深走,遇到叶子节点再往回走

? ? ? ? 2、广度优先遍历:一层一层的去遍历

  • 深度优先遍历
    • 前序遍历(递归法,迭代法)
    • 中序遍历(递归法,迭代法)
    • 后序遍历(递归法,迭代法)
  • 广度优先遍历
    • 层次遍历(迭代法)

前序遍历:中左右? ?中序遍历:左中右? ? ?后序遍历:左右中

最后写一下二叉树的链式存储定义:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

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