使用 Python 查找具有相同概率的最大出现元素索引

在下面的教程中，我们将学习如何使用 Python 编程语言找到列表中出现概率相等的最大出现元素的索引。

那么，让我们开始吧。

理解问题

给定一个重复元素的列表，我们需要找到出现概率相等的最大出现元素的索引。假设我们有一个包含多个元素的数组 {1, 2, 2, 5, 3, 6, 2, 4, 5, 3, 4, 1, 6, 2, 6, 9, 8, 1, 2, 5}。在此数组中，元素 2 出现了五次，索引号分别为 1、2、6、13 和 18。此问题的解决方案以相等的概率随机返回其一个索引。如果数组包含两个最大出现次数，则解决方案应考虑第一个最大出现次数。

让我们看一个例子，演示输入数组及其相应的可能输出。

示例

输入

given_array = [1, 2, 2, 5, 3, 6, 2, 4, 5, 3, 4, 1, 6, 2, 6, 9, 8, 1, 2, 5]

输出

2 是出现频率最大的元素，位于索引号：1

或

2 是出现频率最大的元素，位于索引号：2

或

2 是出现频率最大的元素，位于索引号：6

或

2 是出现频率最大的元素，位于索引号：13

或

2 是出现频率最大的元素，位于索引号：18

所有这些输出都具有相等的概率。

理解解决问题的算法

为了解决这个问题，我们将遵循一个简单的方案。我们将首先遍历数组一次，找到出现频率最大的元素及其频率 n。然后，我们将生成一个介于 1 和 n 之间的随机数 k，并返回数组中出现频率最大的元素的第 k 次出现。

现在让我们通过下面讨论的算法来理解这种方法

算法

步骤 1：我们将定义一个函数，该函数将一个数组作为参数。

步骤 2：在此函数内部，我们将记录字典中所有输入元素的计数。

步骤 3：然后，我们将创建一个 for 循环。

步骤 4：我们将遍历字典。

步骤 5：然后，我们将找出哪个元素首先出现次数最多。

步骤 6：然后，我们将生成一个介于 1 和元素在字典中出现次数之间的随机数。

步骤 7：最后，我们将返回生成的数字作为最大出现元素的索引。

问题解决方案

既然我们已经理解了算法，现在是时候在下面的 Python 程序中实现了，以便找到出现概率相等的最大出现元素的索引。

代码

输出

Given Array : [1, 2, 2, 5, 3, 6, 2, 4, 5, 3, 4, 1, 6, 2, 6, 9, 8, 1, 2, 5]
2 is the Maximum Occurring Element, present at index: 13

说明

在上面的代码片段中，我们导入了所需的库，并定义了一个名为 findMaxOccurringElement() 的函数，该函数接受一个数组作为参数。在此函数内部，我们计算了数组的长度并创建了一个空字典。然后，我们遍历了字典，并根据数组的元素进行了更新。然后，我们初始化了两个变量 - MAX_ELEMENT 和 MAX_SO_FAR - 为可能的最小整数值，表示最大出现元素及其总出现次数。然后，我们遍历了字典，并用当前最大元素及其总频率更新了变量的值。之后，我们生成了一个介于 1 和最大出现元素总频率之间的随机数 k。然后，我们遍历了数组，并打印了该元素第 k 次出现的位置。

对于主函数，我们初始化了给定的数组，为了参考打印了它，并调用了定义的函数来查找出现概率相等的最大出现元素。

结果是，元素 2 在数组 - [1, 2, 2, 5, 3, 6, 2, 4, 5, 3, 4, 1, 6, 2, 6, 9, 8, 1, 2, 5] - 中出现次数最多，其索引值为 13。

所提出解决方案的时间复杂度为 O(n)，其中 n 是输入大小。它需要 O(n) 的额外空间用于字典。

结论

在上面的教程中，我们已经通过 Python 编程语言学习了查找出现概率相等的最大出现元素的索引的方法。我们已经研究了字典如何帮助我们存储每个元素的出现次数，以及如何使用 random 模块的 randrange() 方法。我们用来解决给定问题的方法很简单，时间复杂度为 O(n)；但是，人们可以使用不同的方法来更轻松、更有效地解决此问题。