查找数组中最频繁和最不频繁的元素

在此问题中，给定一个整数数组。我们需要找到数组中出现次数最多的元素和出现次数最少的元素。如果有多个元素具有相同的最高或最低频率，我们可以返回其中任何一个元素。

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

输入: arr = [2, 3, 2, 2, 4, 2]

输出 2

解释: 2 出现 4 次，而 3 和 4 只出现一次。因此，出现频率最高的元素是 2

输入: arr = [2, 3, 2, 2, 4, 2, 3, 3, 4, 3]

输出: 3 或 2

解释: 在这个数组中，2 和 3 出现的次数最多。因此，输出可以是其中任何一个。

输入: arr = [2, 3, 2, 2, 4, 2]

输出: 3 或 4

解释: 3 和 4 在数组中都只出现一次

方法 - 1

解决此问题最基本的方法是运行两个循环。第一个循环遍历每个数组元素。在第二个循环中，计算外层循环当前元素的频率。我们可以跟踪最大频率和最大频率对应的元素。当外层循环完成后，我们将得到出现频率最高的元素及其频率。

代码

输出

2

时间复杂度:- 这种方法的时间复杂度是非线性或二次的，因为我们对整个数组使用了两个循环。因此，总时间复杂度为 O(N ^ 2)。

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

通过进行微小的修改，使代码能够找到出现频率最低的元素。为了找到出现频率最低的元素，我们将在外层循环结束后查找最低频率计数。我们将检查当前计数是否小于最低频率计数。如果是，我们将更新最低频率计数和对应的元素。

代码

输出

4

方法 - 2

# 我们可以通过对数组进行排序来优化上述方法。如果对数组进行排序，我们可以用一个单独的循环找到答案。在每次迭代中，我们将检查当前频率是否超过最大频率，然后更新最大频率。

代码

输出

2

时间复杂度: 对数组进行排序的时间复杂度为 O(log n)。线性 for 循环的时间复杂度为 O(n)。因此，最终的时间复杂度为 O(n + log n)。

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

现在，我们将看到如何使用相同的逻辑来找到出现频率最低的元素。为了找到出现频率最低的元素，我们将检查当前计数是否小于迄今为止的最低频率计数。如果是，我们将更新最低频率计数和对应的元素。

代码

输出

4

方法 - 3

我们可以使用哈希技术进一步降低解决方案的时间复杂度。我们将创建一个哈希表，其中包含数组中的不同元素以及给定数组中特定元素出现的次数。我们将使用键值对来存储，其中键是不同的元素，值是键元素的频率。最后，我们将遍历哈希表并找到出现频率最高的元素。

代码

输出

2

时间复杂度: 我们在此问题中使用了两个线性循环；因此，时间复杂度将是线性的，即 O(n)。

辅助空间: 我们使用了额外的空间来存储哈希表；因此，此解决方案的空间复杂度为 O(n)。

为了找到出现频率最低的元素，我们将在哈希表中搜索最低频率，并返回相应的元素。

代码

输出

4

方法 - 4

解决此问题的一个更有效的方法是使用摩尔投票算法。

在摩尔投票算法中，我们将任何数组元素假定为结果。然后，我们遍历整个数组并进行投票。在投票过程中，如果我们发现当前元素与假定的结果相同，则增加计数；否则，如果当前元素不同，则减少频率计数。如果在循环的任何时候计数变为零，则意味着当前的假定结果不是答案，我们将假定结果更新为循环的当前元素。通过这种方式，当循环完成时，我们将得到获得最多票数的元素；因此，它将是我们期望的输出。

下面是展示如何执行摩尔投票算法并解决此问题的 Python 代码。

代码

输出

3

时间复杂度: 我们使用了一个线性 for 循环在元素之间进行投票。因此，此解决方案的时间复杂度将是线性的，即 O(n)。

辅助空间: 在此解决方案中，我们没有使用任何额外的空间；因此，空间复杂度将是常数，即 O(1)。