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

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) {}
};