查找数组中出现次数最多的 k 个数

引言

本文将探讨一种有效的 Python 算法，用于识别数组中出现频率最高的“k”个数字。查找出现频率最高的元素是一个常见的数据分析挑战，具有多种用途，包括识别热门电子商务商品、研究用户行为以及处理大型数据集。

识别问题

在深入技术细节之前，让我们明确定义问题。我们的目标是在给定整数数组的情况下，识别数组中出现频率最高的“k”个数字。无论元素在数组中出现的顺序如何，我们都必须找到出现频率最高的元素。

例如，考虑以下输入数组

[1, 3, 4, 3, 2, 4, 4, 2, 5]

假设 k = 2，则输出应为

[4, 3]

数组中 4 和 3 的最高出现频率均为 3。

哈希表

哈希映射方法涉及遍历数组并维护一个字典以确定每个元素的出现次数。计数后，我们根据频率按降序对字典进行排序，然后提取前“k”个元素。这种方法的简单性源于 Python 提供了内置数据结构（如字典）来成功处理此任务。

堆

堆方法使用最小堆跟踪出现频率最高的“k”个元素。每次我们遍历数组时遇到新元素时，堆都会相应地更新。如果堆的大小大于“k”，则删除出现频率最低的元素。当处理大型数据集或当“k”明显小于数组大小时，堆方法特别有用，因为它内存效率高。

算法的应用

我们将详细概述哈希映射和堆方法的 Python 代码。

使用哈希映射

频率映射构建

首先，我们开发一个 Python 函数，该函数使用哈希映射策略来识别具有最高频率的“k”个数字

使用哈希映射查找出现次数最多的 k 个数字的 Python 代码

输出

[(1, 3), (2, 2)]

此代码片段从头开始创建 frequency_map 字典。下一步是遍历输入数组 arr 并使用 get() 方法检索每个元素的当前频率计数。当第一次遇到元素时，get() 方法返回 0，我们在此值上加 1。此过程对数组中的每个元素重复，从而生成一个字典，其中元素的频率作为键，其值作为值。

*频率映射已排序。

现在我们可以通过根据频率按降序对频率映射进行排序来提取前“k”个元素。我们可以将以下步骤添加到 find_k_most_frequent() 函数中

使用哈希映射和排序查找出现次数最多的 k 个数字的 Python 代码

输出

[1, 2]

字典的键值对通过 items() 方法作为元组列表返回，我们根据每个元组的第二个元素的频率对该列表进行排序。然后，在从排序列表中删除前“k”个元素后，返回结果。

使用堆构建最小堆

要使用堆方法查找出现次数最多的“k”个数字，我们必须首先创建一个类似于哈希映射方法的 Python 函数

使用堆查找出现次数最多的 k 个数字的 Python 代码

输出

[1, 2]

此代码片段中使用了 heapq 模块，该模块提供了在 Python 中实现堆的函数。为了用作最小堆，我们创建一个名为 min_heap 的空列表。与哈希映射方法类似，我们在遍历输入数组 arr 时更新 frequency_map。

处理新元素

• 我们使用 heappush() 函数将 (frequency, element) 元组推入最小堆中的每个频率映射元素。堆将根据每个元组的第一个元素的频率进行排序，这要归功于此元组结构。
• 如果堆大小大于“k”，则使用 heappop() 函数从堆中删除最小元素。最小堆中具有最高频率的“k”个元素有效地通过此过程进行维护。
• 最后，我们从最小堆中取出组件并返回它们。我们使用切片 ([::-1]) 反转列表，以首先获得具有最高频率的元素，因为元素列表将按频率升序排列。

时间和空间复杂度分析

哈希映射方法

排序步骤（需要 O(n log n) 时间，其中“n”是数组大小）支配了哈希映射方法的时间复杂度。

由于我们必须存储频率映射，其中可以包含数组中的每个唯一元素，因此空间复杂度为 O(n)。

大规模方法

堆中的插入和删除操作需要 O(log k) 时间，我们对“n”个元素执行这些操作，因此堆方法的时间复杂度为 O(n log k)。

由于我们只需要在最小堆中存储“k”个元素，因此空间复杂度为 O(k)。

比较方法

在探索哈希映射和堆方法之后，让我们评估它们在各种场景中的表现。

小“k”值

当“k”值相对于数组大小较小时，堆方法可以优于哈希映射方法。这是因为堆方法使用的内存更少，并且可能会导致更快的排序，因为它只在最小堆中维护“k”个元素。

大“k”值

另一方面，当“k”值接近数组大小或“k”明显大于数组中不同元素的数量时，哈希映射方法可能效果更好。排序一个小型频率映射可能比维护一个大型最小堆更有效。

数组大小与“k”

一般来说，如果数组大小“n”明显大于“k”，则堆方法可能更内存高效，因此更适合处理大数据场景。

实际应用

元素频率问题在许多领域都有实际应用，包括

基于互联网的平台

分析客户购买历史可以帮助电子商务平台识别热门产品并增强产品推荐系统。企业可以通过识别购买频率最高的产品来专注于营销和扩大这些产品的可用性。

社交媒体分析

分析社交媒体分析中的趋势话题和标签可以揭示用户兴趣信息，并有助于创建有趣的内容。社交媒体平台可以通过识别讨论最频繁的话题来提高用户参与度和内容发现。

客户行为分析

了解客户行为和偏好对于企业做出明智决策至关重要。频率分析可用于帮助企业识别最受欢迎的功能或服务，从而更好地调整其产品以满足客户需求。