数据结构-PHP 输出数组中出现频率最高的前 k 个

亦凉 2023-09-24 08:16 141阅读 0赞

数据结构-PHP 输出数组中出现频率最高的前 k 个1. 问题描述2.问题分析2.1 第一步：去重统计分析2.2 第二步：选出上述二分搜索树中统计次数最大的前 k 个2.2.1 使用基于二分搜索树的 Map 排序2.2.2 使用基于最小堆维持的 k 个最大元素

3.PHP 代码3.1 BinarySearchTreeMap 基于二分搜索树的映射(Map)3.2 MinHeap 最小堆3.3 ArrayStruct 数组类3.4 output\_map.php 输出演示

这篇文章主要是通过一个问题实现过程，选择合适的数据结构，结合之前介绍过的 和 两种数据结构，可以将问题实现过程的时间复杂度降低。

解决问题的思路主要分为两步：

第一步主要是去重，并且需要统计出现元素的次数。第二步将统计次数出现最高的前 k 个提取出来输出。尽可能的降低时间复杂度。

2.1 第一步：去重统计分析

若想要统计元素出现的次数，必须要要把全部数组元素遍历一次，此时复杂度为 ，若需要统计元素的次数，则每次出现的时候需要将元素出现的次数 操作，此时最好的更新查找操作是复杂度为 的数据结构，符合这种 的数据结构，并且能快速查找的数据结构就是 ，其原理图如下：

![在这里插入图片描述][9e8cb6534e0a886a0777430271e75683.png]

Tips：若该二分搜索树上已经存在元素 ，添加相同 的时候只需要将 值 ，这样保证了数据的查找速度，也能保证 的作用。此时综合的时间复杂度为 。

2.2 第二步：选出上述二分搜索树中统计次数最大的前 k 个

2.2.1 使用基于二分搜索树的 Map 排序

，并且将数据转移到另外一个 ，但此时 和 的值，比如原理 表示 统计的次数是 ，转移到新的 上 其目的就是为了保证统计次数有序，其原理图如下：

![在这里插入图片描述][9d64c7b2b80e103d8d2f229a7e7ffcd7.png]

Tips：此时可以保持新的 上 有序，综合的时间复杂度为 。

2.2.2 使用基于最小堆维持的 k 个最大元素

，并且将数据转移到只保持 个元素的 中，若元素比 中的最小元素还要大，那么就需要把新元素 ，以此类推，达到提取 值前 个最大元素：

![在这里插入图片描述][dffcc3511aa7990617e4beca9a2fe308.png]

Tips：图中最小堆展示的是出现次数频率最高的前 个频率数，其实存储可以使用 这种格式去存储，综合时间复杂度为 ，这个复杂度比 要小。

3.1 BinarySearchTreeMap 基于二分搜索树的映射(Map)

该类中 可以向数据中添加 ， 方法可以获取 对于的 ， 方法可以更新 对于的 值， 方法可以将 中的数据转移到 中，并保持前 个最大:

3.2 MinHeap 最小堆

这是一个基于 实现的 ，每个节点包含 和 两个属性，其中 表示频率， 表示元素值， 和 操作是基于 值比较的：

3.3 ArrayStruct 数组类

这是一个数组类，能实现基本数组元素的增删改查操作，并且动态扩容：

3.4 output\_map.php 输出演示

输出结果如下：

![在这里插入图片描述][f02d8aa7fc880ac026545e5b354982f2.png]

代码仓库 ：https://gitee.com/love-for-poetry/data-structure

扫码关注爱因诗贤

![在这里插入图片描述][96815fd954bd8fef2c989770c64c35cc.png]

[9e8cb6534e0a886a0777430271e75683.png]: https://img-blog.csdnimg.cn/img_convert/9e8cb6534e0a886a0777430271e75683.png
[9d64c7b2b80e103d8d2f229a7e7ffcd7.png]: https://img-blog.csdnimg.cn/img_convert/9d64c7b2b80e103d8d2f229a7e7ffcd7.png
[dffcc3511aa7990617e4beca9a2fe308.png]: https://img-blog.csdnimg.cn/img_convert/dffcc3511aa7990617e4beca9a2fe308.png
[f02d8aa7fc880ac026545e5b354982f2.png]: https://img-blog.csdnimg.cn/img_convert/f02d8aa7fc880ac026545e5b354982f2.png
[96815fd954bd8fef2c989770c64c35cc.png]: https://img-blog.csdnimg.cn/img_convert/96815fd954bd8fef2c989770c64c35cc.png