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

码农天地 - 2020-10-30 12:23:09

这篇文章主要是通过一个问题实现过程，选择合适的数据结构，结合之前介绍过的 基于二分搜索树实现的映射(Map) 和 最小堆两种数据结构，可以将问题实现过程的时间复杂度降低。

1. 问题描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

2.问题分析

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

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

若想要统计元素出现的次数，必须要要把全部数组元素遍历一次，此时复杂度为 O(n)，若需要统计元素的次数，则每次出现的时候需要将元素出现的次数 +1 操作，此时最好的更新查找操作是复杂度为 O(logn) 的数据结构，符合这种 key-value 的数据结构，并且能快速查找的数据结构就是 基于二分搜索树实现的映射(Map)，其原理图如下：

Tips：若该二分搜索树上已经存在元素 key，添加相同 key 的时候只需要将 value 值 +1 ，这样保证了数据的查找速度，也能保证 统计出现频率 的作用。此时综合的时间复杂度为 O(nlogn)。2.2 第二步：选出上述二分搜索树中统计次数最大的前 k 个2.2.1 使用基于二分搜索树的 Map 排序

遍历映射(Map)，并且将数据转移到另外一个 新的基于二分搜索树实现的映射(Map)，但此时 key 和 value 的值对调，比如原理 key=3，value=5 表示 3 统计的次数是 5，转移到新的 Map 上 key=5,value=3 其目的就是为了保证统计次数有序，其原理图如下：

Tips：此时可以保持新的 字典（Map）上 value 有序，综合的时间复杂度为 O(nlogn)。2.2.1 使用基于最小堆维持的 k 个最大元素

遍历映射(Map)，并且将数据转移到只保持 k 个元素的 最小堆 中，若元素比 最小堆 中的最小元素还要大，那么就需要把新元素 替换堆顶，以此类推，达到提取 value 值前 k 个最大元素：

Tips：图中最小堆展示的是出现次数频率最高的前 k 个频率数，其实存储可以使用 ["value" => 3,"count" => "7"] 这种格式去存储，综合时间复杂度为 O(nlogk)，这个复杂度比 O(nlogn) 要小。3.PHP 代码3.1 BinarySearchTreeMap 基于二分搜索树的映射(Map)

该类中add() 可以向数据中添加 key-value，get() 方法可以获取 key 对于的 value，set() 方法可以更新 key 对于的 value 值，traverseMinHeap() 方法可以将 Map 中的数据转移到 最小堆 中，并保持前 k 个最大:

class BinarySearchTreeMap implements Map
{
    public $root;
    public $size;
    public function __construct() {
        $this->root = null;
        $this->size = 0;
    }
    /**
     * 获取映射(Map)中某个key对应的value
     * @param $key
     * @return |null
     */
    public function get($key) {
        $node = $this->recursionGet($key, $this->root);
        return $node == null ? null : $node->value;
    }
    /**
     * 递归获取 key 对应的节点
     * @param $key
     * @param $root
     * @return |null
     */
    private function recursionGet($key, $root) {
        if ($root == null) {
            return null;
        } elseif ($key == $root->key) {
            return $root;
        } elseif ($key < $root->key) {
            return $this->recursionGet($key, $root->left);
        } else {
            return $this->recursionGet($key, $root->right);
        }
    }
    /**
     * 添加 key-value 数据
     * @param $key
     * @param $value
     */
    public function add($key, $value): void {
        $this->root = $this->recursionAdd($key, $value, $this->root);
    }
    /**
     * 递归添加数据
     * @param $key
     * @param $value
     * @param $root
     */
    private function recursionAdd($key, $value, $root) {
        if ($root == null) {
            $root = new Node($key, $value);
            $this->size++;
        } elseif ($key == $root->key) {
            $root->value = $value;
        } elseif ($key < $root->key) {
            $root->left = $this->recursionAdd($key, $value, $root->left);
        } else {
            $root->right = $this->recursionAdd($key, $value, $root->right);
        }
        return $root;
    }
    /**
     * 查看map是否包含某个key
     * @param $key
     * @return bool
     */
    public function contains($key): bool {
        $node = $this->recursionGet($key, $this->root);
        return $node != null;
    }
    /**
     * 递归查看map是否存在某个 key
     * @param $key
     * @param $root
     * @return bool
     */
    private function recursionContains($key, $root) {
        if ($root == null) {
            return false;
        } elseif ($key == $root->key) {
            return true;
        } elseif ($key < $root->key) {
            return $this->recursionContains($key, $root->left);
        } else {
            return $this->recursionContains($key, $root->right);
        }
    }
    /**
     * 修改 key 对应的 value
     * @param $key
     * @param $value
     */
    function set($key, $value) {
        $node = $this->recursionGet($key, $this->root);
        if ($node == null) {
            echo "不存在该节点";
            exit;
        }
        $node->value = $value;
    }
    public function traverseMinHeap($minHeap, $k) {
        $this->recursionTraverse($this->root, $minHeap, $k);
    }
    private function recursionTraverse($root, $minHeap, $k) {
        if ($root != null) {
            $this->recursionTraverse($root->left, $minHeap, $k);
            if ($minHeap->getSize() < $k) {
                $minHeap->add(['key' => $root->key, 'value' => $root->value]);
            } else {
                $min = $minHeap->findMin();
                if ($root->value > $min['value']) {
                    $minHeap->replaceMin(['key' => $root->key, 'value' => $root->value]);
                }
            }
            $this->recursionTraverse($root->right, $minHeap, $k);
        }
    }
    /**
     * 获取映射 Map 中 key-value 数量
     * @return int
     */
    public function getSize(): int {
        return $this->size;
    }
}
class Node
{
    public $key;
    public $value;
    public $left = null;
    public $right = null;
    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
    }
}

3.2 MinHeap 最小堆

这是一个基于数组类(ArrayStruct) 实现的 最小堆，每个节点包含 key 和 value 两个属性，其中 key 表示频率，value 表示元素值，上浮(siftUp) 和 下沉（siftDown） 操作是基于 key 值比较的：

class MinHeap
{
    private $array = null;
    /**
     * 构造函数 初始化堆的容量
     * MinHeap constructor.
     * @param int $capacity
     */
    public function __construct(int $capacity = 10) {
        $this->array = new ArrayStruct($capacity);
    }
    /**
     * 返回堆的元素个数
     * @return int
     */
    public function getSize(): int {
        return $this->array->getSize();
    }
    /**
     * 判断堆是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->array->isEmpty();
    }
    /**
     * 计算某个索引 $i 节点父亲节点索引值 $i父+1 = ($i+1)/2 取整，即 $i父 = ($i-1)/2 取整
     * @param $i
     * @return int
     */
    private function parent($i): int {
        if ($i == 0) {
            echo "索引 0 是没有父亲节点的";
            exit;
        }
        return (int)(($i - 1) / 2);
    }
    /**
     * 计算某个索引 $i 节点左儿子节点索引值 $i左+1 = ($i+1)*2 取整，即 $i左 = 2*$i+1
     * @param $i
     * @return int
     */
    private function leftSon($i): int {
        return $i * 2 + 1;
    }
    /**
     * 计算某个索引 $i 节点右儿子节点索引值 $i右+1 = ($i+1)*2+1 取整，即 $i左 = 2*$i+2
     * @param $i
     * @return int
     */
    private function rightSon($i): int {
        return $i * 2 + 2;
    }
    /**
     * 向堆中添加元素
     * @param $e
     */
    public function add($e): void {
        $this->array->addLast($e);
        $this->siftUp($this->array->getSize() - 1);
    }
    /**
     * 元素上浮
     * @param $i
     */
    private function siftUp($i) {
        while ($i > 0 && $this->array->get($this->parent($i))['value'] > $this->array->get($i)['value']) {
            $this->swsp($i, $this->parent($i));
            $i = $this->parent($i);
        }
    }
    /**
     * 元素下沉
     * @param $i
     */
    private function siftDown($i) {
        while ($i < $this->array->getSize() / 2) {
            $leftSon = $this->array->get($this->leftSon($i));
            $rightSon = $this->array->get($this->rightSon($i));
            if (!empty($leftSon) && empty($rightSon) && $this->array->get($i)["value"] > $leftSon["value"]) {
                $this->swsp($i, $this->leftSon($i));
                $i = $this->leftSon($i);
            } elseif (empty($leftSon) && !empty($rightSon) && $this->array->get($i)["value"] > $rightSon["value"]) {
                $this->swsp($i, $this->rightSon($i));
                $i = $this->rightSon($i);
            } elseif (!empty($leftSon) && !empty($rightSon) && ($this->array->get($i)["value"] > $rightSon["value"] || $this->array->get($i)["value"] > $leftSon["value"])) {
                if ($rightSon["value"] > $leftSon["value"]) {
                    $this->swsp($i, $this->leftSon($i));
                    $i = $this->leftSon($i);
                } else {
                    $this->swsp($i, $this->rightSon($i));
                    $i = $this->rightSon($i);
                }
            } else {
                break;
            }
        }
    }
    /**
     * 查看堆中最大的元素
     * @return mixed
     */
    public function findMin() {
        if ($this->array->isEmpty()) {
            echo "堆是空的";
            exit;
        }
        return $this->array->get(0);
    }
    public function getMin() {
        $max = $this->findMin();
        $this->array->set(0, $this->array->removeLast());
        //删除操作
        if ($this->array->getSize() > 1) {
            $this->siftDown(0);
        }
        return $max;
    }
    public function replaceMin($e) {
        $min = $this->findMin();
        $this->array->set(0, $e);
        $this->siftDown(0);
        return $min;
    }
    /**
     * 交换堆中元素值
     */
    public function swsp($i, $parentI) {
        $parentE = $this->array->get($parentI);
        $e = $this->array->get($i);
        $this->array->set($i, $parentE);
        $this->array->set($parentI, $e);
    }
    public function toString() {
        return $this->array->toString();
    }
}

3.3 ArrayStruct 数组类

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

<?php
/**
 * 数据结构-数组的实现
 * Class ArrayStruct
 */
class ArrayStruct
{
    //用于存放数据
    protected $data = [];
    //用于标记数组大小
    protected $size = 0;
    //用于标记数组的容量
    protected $capacity = 10;
    /**
     * 构造函数 定义数组容量
     * ArrayStruct constructor.
     * @param int $capacity
     */
    public function __construct(int $capacity = 10) {
        $this->capacity = $capacity;
    }
    /**
     * 获取数组元素个数
     * @return int
     */
    public function getSize(): int {
        return $this->size;
    }
    /**
     * 获取数组的容量
     * @return int
     */
    public function getCapacity(): int {
        return $this->capacity;
    }
    /**
     * 判断数组是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->size == 0;
    }
    /**
     * 向数组指定位置插入元素
     * @param int $index
     * @param $e
     * @throws Exception
     */
    public function add(int $index, $e): void {
        if ($this->size == $this->capacity) {
            $this->resize(2); //扩大到原来的2倍
        }
        if ($index < 0 || $index > $this->size) {
            echo "添加位置超出数组大小";
            exit;
        }
        //为了方便理解，[1,2,4,5,6],假设 $index = 3; $e = 100,插入之后[1,2,4,100,5,6]
        for ($i = $this->size; $i >= $index; $i--) {
            $this->data[$i] = $this->data[$i - 1];
        }
        $this->data[$index] = $e;
        $this->size++;
    }
    public function set($index, $e) {
        if ($index < 0 || $index > $this->size) {
            echo "添加位置超出数组范围";
            exit;
        }
        $this->data[$index] = $e;
    }
    /**
     * 向数组末尾添加元素
     * @param $e
     * @throws Exception
     */
    public function addLast($e): void {
        $this->add($this->size, $e);
    }
    /**
     * 向数组开头插入元素
     * @param $e
     * @throws Exception
     */
    public function addFirst($e): void {
        $this->add(0, $e);
    }
    /**
     * 获取 index 位置数组元素
     * @param int $index
     * @return mixed
     */
    public function get(int $index) {
        if ($index < 0 || $index > $this->size) {
            echo "index值超出元素的位置范围，";
            exit;
        }
        return $this->data[$index];
    }
    /**
     * 获取数组末尾元素
     * @return mixed
     */
    public function getLast() {
        return $this->get($this->size - 1);
    }
    /**
     * 获取数组开头元素
     * @return mixed
     */
    public function getFirst() {
        return $this->get(0);
    }
    /**
     * 判断数组中是否存在某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool {
        for ($i = 1; $i < $this->size; $i++) {
            if ($this->data[$i] == $e) {
                return true;
            }
        }
        return false;
    }
    /**
     * 查某个元素在数组的位置索引值，若不存在则返回 -1
     * @param $e
     * @return int
     */
    public function find($e): int {
        for ($i = 0; $i < $this->size; $i++) {
            if ($this->data[$i] == $e) {
                return $i;
            }
        }
        return -1;
    }
    /**
     * 删除数组指定位置元素，返回删除元素的值
     * @param $index
     * @return mixed
     */
    public function remove($index) {
        if ($index < 0 || $index > $this->size) {
            echo "index值超出元素的位置范围，";
            exit;
        }
        $e = $this->data[$index];
        for ($i = $index; $i < $this->size - 1; $i++) {
            $this->data[$i] = $this->data[$i + 1];
        }
        $this->size--;
        $this->data[$this->size] = null;  //loitering objects ! =memory
        /** 若当前数组大小，小于容量的一半，则重新分配一半的数组空间大小 **/
        if ($this->size <= $this->capacity / 4 && $this->capacity % 2 == 0) {
            $this->resize(0.5);
        }
        return $e;
    }
    /**
     * 删除数组首个元素，返回删除元素的值
     */
    public function removeFirst() {
        return $this->remove(0);
    }
    /**
     * 删除数组首个元素，返回删除元素的值
     */
    public function removeLast() {
        return $this->remove($this->size - 1);
    }
    /**
     * 删除数组中特定元素
     * @param $e
     */
    public function removeElement($e) {
        for ($i = 0; $i < $this->size; $i++) {
            if ($this->data[$i] == $e) {
                $this->remove($i);
                $this->removeElement($e);
                break;
            }
        }
    }
    /**
     * 数组扩容，若是其他语言，如JAVA这里需要重新开辟空间
     * @param $factor
     */
    protected function resize($factor) {
        $this->capacity = $factor * $this->capacity;
    }
    /**
     * 将数组转化为字符串
     * @return string
     */
    public function toString(): string {
        $str = "[";
        for ($i = 0; $i < $this->size; $i++) {
            $value_str = is_numeric($this->data[$i]) ? $this->data[$i] : "'{$this->data[$i]}'";
            $str       .= $i . " => " . $value_str . ",";
        }
        $str = trim($str, ",");
        $str .= "]";
        return $str;
    }
}

3.4 output_map.php 输出演示

<?php
//require 'LinkedListMap.php';
//
//$map = new LinkedListMap();
//$map->add("school","wuhan");
//$map->add("name","爱因诗贤");
//$map->add("age",18);
//$map->add("weight",65);
//$map->remove("school");
//
//print_r($map);
require 'BinarySearchTreeMap.php';
require $root . "/MinHeap/MinHeap.php";
$nums = [5,-3,9,1,7,7,9,10,2,2,10,10,3,-1,3,7,-9,-1,3,3];
$k   = 3;
$map = new BinarySearchTreeMap();
foreach ($nums as $key) {
    $value = $map->get($key);
    if ($value != null) {
        $map->set($key, $value + 1);
    } else {
        $map->add($key, 1);
    }
}
$minHeap = new MinHeap();
$map->traverseMinHeap($minHeap, $k);
//print_r($minHeap);
$reArr = [];
while (!$minHeap->isEmpty()) {
    $arr = $minHeap->getMin();
    $reArr[] = $arr["key"];
}
print_r($reArr);

输出结果如下：

代码仓库：https://gitee.com/love-for-po...

扫码关注爱因诗贤

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。