Python解决方案：计算排序数组中某个元素的出现次数

在此问题中，我们给定一个整数排序数组。我们需要找到给定数字在给定数组中重复的次数。

让我们看一些例子来理解这个问题

输入： 数组 = {1, 1, 1, 1, 3, 3, 4}, x = 1

输出： 4 整数 x 在给定数组中出现 4 次

输入： 数组 = {1, 2, 2, 3, 4, 4, 5, 5},

x = 2

输出 2

输入： 数组 = {1, 2, 2, 3, 4, 4, 5, 5},

x = 3

输出 1

输入： 数组 = {1, 2, 2, 3, 4, 4, 5, 5},

x = 6

输出 -1

整数 6 不存在于给定数组中

方法 - 1

在此方法中，我们将使用线性搜索来计算给定整数在数组中重复的次数。我们可以使用线性循环遍历数组中的元素，并维护一个变量来计算特定数字的出现次数。

代码

输出

The frequency of 2 is 2

时间复杂度： 此方法的时​​间复杂度是线性的，因为我们使用了线性循环来遍历数组的元素。因此，时间复杂度为 O(n)。

空间复杂度： 我们没有使用额外的空间来解决这个问题；因此，空间复杂度是常数 O(1)。

方法 - 2

在此方法中，我们将使用二分查找算法来解决此问题。我们将找到 x 的索引，并使用 for 循环计算索引左侧和右侧的出现次数。

代码

输出

The frequency of 2 is 2

时间复杂度： 程序将花费 log n 的时间复杂度使用二分查找搜索元素 x，然后花费线性时间 O(c) 来计算出现次数。因此，该程序的最终时间复杂度为 O(log n + c)，其中 c 是出现次数。

空间复杂度： 由于二分查找的递归堆栈，此方法的空间复杂度为 O(log n)。

方法 - 3

在此方法中，我们也使用二分查找算法。但是，我们将优化该算法以充分利用二分查找算法。以下是我们为解决此问题将遵循的步骤

我们将创建一个函数来对给定的排序数组执行二分查找算法。此函数将返回数组中给定元素 x 的第一次出现索引。

我们将定义另一个函数来执行二分查找算法。此函数将返回元素 x 在数组中最后一次出现索引。

最后，我们将创建一个函数来调用这两个函数并返回出现次数。

代码

输出

The frequency of 2 is 2

时间复杂度： 我们使用二分查找两次来查找第一次和最后一次出现索引，这需要 O(Log n) 的时间。除了二分查找，我们没有使用任何其他循环；因此，最终时间复杂度为 O(log n)。

辅助空间： 我们没有使用任何额外的空间，因此空间复杂度是常数，即 O(1)。

方法 - 4

我们将使用内置的 Python count() 函数来查找元素 x 的频率。

代码

输出

The frequency of 2 is 2

时间复杂度： count 函数的时间复杂度为 O(n)。因此，该程序的最终时间复杂度为 O(n)。

辅助空间： 我们没有使用任何额外的空间；因此，空间复杂度是常数，即 O(1)。

方法 - 5

在此方法中，我们将使用哈希方法来计算给定排序数组中 x 的出现次数。在 Python 中，我们可以使用内置字典数据结构来使用哈希技术。

我们将遵循以下步骤创建程序。

我们将首先初始化一个空字典。我们将此字典称为 map。我们将在此字典中存储所有元素的频率。因此，此字典将是一个无序的列表，包含给定排序数组的元素，映射到该排序数组中特定元素的频率。

现在，我们将遍历排序数组并将频率存储在 map 中。

然后，我们将使用 find() 方法在无序 map 中查找元素 x，从而找到键 x 的值，即 x 在给定排序数组中的出现次数。

代码

输出

The frequency of 2 is 2

时间复杂度： 我们使用线性循环遍历数组并将每个元素的频率存储在字典中；因此，时间复杂度是线性的，即 O(n)，其中 n 是排序数组的长度

辅助空间： 我们使用字典来存储元素的频率；因此，空间复杂度为 O(k)，其中 k 是排序数组中不同元素的数量。