查找下一个频率更高的元素

在本教程中，我们将学习如何编写 Python 程序来查找下一个更高频率的元素。我们将使用各种方法来解决这个问题。让我们先来理解问题陈述。

我们给定一个数组，需要确定最接近的右侧具有更高频率的元素。如果不存在这样的元素，则将其赋值为 -1。让我们来理解下面的例子。

示例 -

输入： a = [5, 3, 7, 2, 3, 8, 1]

输出 [-1, 7, -1, -1, 2, -1, -1]

说明

给定数组 a = [5, 3, 7, 2, 3, 8, 1]

每个元素的频率是：[1, 2, 1, 2, 2, 1, 1]

输出代表具有更高频率的最接近的右侧元素。

让我们为数组 a[] 中的每个元素确定下一个更高频率 (NGF) 元素。

1. 对于元素 a[0] = 1，其频率为 3，其右侧没有其他元素的频率更高，因此 NGF 元素为“-1”。
2. 对于元素 a[1] = 1（频率为 3），其右侧也没有其他元素的频率更高，因此其 NGF 为“-1”，与 a[0] 类似。
3. 对于元素 a[2] = 2（频率为 2），NGF 元素是 1，位于位置 6，频率为 3，高于 2。
4. 对于元素 a[3] = 3（频率为 1），NGF 元素是 2，位于位置 5，频率为 2，高于 1。
5. 对于元素 a[4] = 4（频率为 1），NGF 元素是 2，位于位置 5，频率为 2，高于 1。
6. 对于元素 a[5] = 2（频率为 2），NGF 元素是 1，位于位置 6，频率为 3，高于 2。
7. 对于元素 a[6] = 1，其右侧没有元素，因此其 NGF 为“-1”。

通过这种方式，我们根据每个元素的频率和位置来确定 NGF 元素。

让我们使用朴素方法来解决这个问题。

解法 -1：朴素方法

哈希技术是一种直接的方法，其中我们使用列表中的值作为索引来存储每个元素的频率。此方法只需要遍历数组一次。然后，我们使用两个循环

1. 外层循环逐个选择每个元素。
2. 内层循环搜索第一个频率高于当前元素频率的元素，其中我们使用列表中的值作为索引来存储每个元素的频率。此方法只需要遍历数组一次。然后，我们使用两个循环

• 外层循环逐个选择每个元素。
• 内层循环搜索第一个频率高于当前元素频率的元素。

让我们理解下面的代码片段。

示例 -

输出

[-1, -1, 1, 2, 2, 1, -1]

解释 -

让我们来理解上面代码的分步解释。

1. 首先，我们定义 nextGreaterFrequencyElement() 函数。它计算输入数组中每个元素的频率，并将此频率信息存储在名为 frequency 的单独列表中。
2. 外层循环使用变量 i 迭代输入数组的每个元素。
3. 对于每个元素 arr[i]，它启动一个内层循环，该循环使用变量 j 从 i+1 迭代到数组末尾。
4. 在内层循环中，它检查当前元素 arr[i] 的频率是否小于位置 j 处元素的频率。如果为真，则 arr[j] 是 arr[i] 的 NGF，因此它将 arr[j] 存储在结果列表中。否则，它在内层循环中继续搜索 NGF。
5. 如果内层循环在未找到频率更高的 NGF 时完成，则将 -1 分配给当前元素 arr[i] 作为 NGF。
6. 将 NGF 或 -1 值附加到结果列表中的每个元素。
7. 处理完外层循环中的所有元素后，结果列表包含每个元素的 NGF（或 -1）。
8. 然后返回结果列表作为最终输出。

该代码通过使用频率信息和嵌套循环有效地计算每个元素的 NGF。它为每个元素提供 NGF 或 -1，如输出和说明中所述。

解法 - 2：使用堆栈（高效方法）

在此方法中，我们将使用堆栈数据结构来有效地解决此问题。让我们来理解以下步骤 -

1. 首先，我们初始化一个空堆栈和一个字典来存储数组中每个元素的频率。
2. 然后，我们初始化一个空结果列表来存储 NGF 元素。
3. 我们以反向顺序遍历输入数组。反向迭代很重要，因为我们要查找右侧的下一个更高频率元素。
4. 按反向顺序遍历每个元素
   • 从字典中检查元素的频率。
   • 当堆栈不为空且当前元素的频率大于或等于堆栈顶部元素的频率时，从堆栈中弹出元素并将 NGF 标记为当前元素。
   • 将当前元素推入堆栈。
5. 如果在循环结束后堆栈中仍有元素，则意味着这些元素的右侧没有更高频率的元素。在这种情况下，将 -1 分配给这些元素的 NGF。
6. 结果列表现在包含数组中每个元素的 NGF，并且顺序正确。

通过使用堆栈有效跟踪下一个更高频率的元素，此方法可以找到 NGF 值，其时间复杂度为 O(n)，其中 n 是输入数组中的元素数量。它比涉及嵌套循环的暴力方法更有效。

让我们理解下面的代码片段。

示例 -

输出

NGF elements for each element: [-1, -1, -1, -1, -1]

解法 - 3 暴力方法

该方法很简单：首先，我们将所有元素的频率存储在一个映射中。然后，我们将所有元素按反向顺序推入堆栈。由于堆栈遵循后进先出 (LIFO) 原则，我们遍历向量，使用堆栈和映射为向量中的每个元素查找下一个更高频率 (NGF)。这种高效技术使我们能够确定数组中每个元素的 NGF。

让我们理解以下示例 -

示例 -

输出

1 --> -1
1 --> -1
2 --> 1
3 --> 2
4 --> 2
2 --> 1
1 --> -1

解释 -

让我们来理解上面代码的流程 -

1. 首先，我们从 collections 模块导入 defaultdict 类。此类别用于创建具有默认值的字典。
2. 然后我们定义一个函数 find_next_greater_frequency_element(arr)，该函数以列表 arr 作为输入。
3. 我们使用 defaultdict(int) 初始化一个字典 mp。此字典将存储输入数组中每个元素的频率。
4. 然后我们创建一个空列表 s。此列表将用作堆栈，用于按反向顺序存储元素。
5. 遍历输入数组 arr 并更新 mp 字典以计算每个元素的频率。
6. 通过反向遍历输入数组并将元素附加到它来创建一个堆栈 s。这会反转元素的顺序。
7. 现在，按原始顺序遍历原始输入数组。
8. 对于每个元素 arr[i]，从 mp 字典中检索其频率并将其存储在变量 x 中。
9. 初始化一个标志为 True。此标志将用于确定是否存在下一个更高频率 (NGF) 元素。
10. 创建堆栈 s 的副本并将其存储在变量 ss 中，并使用 while 循环遍历 ss 中的元素。
11. 检查 ss 中的最后一个元素的频率 (ss[-1]) 是否大于频率 x。如果是，则打印当前元素 arr[i] 和 NGF 元素 ss[-1]，将标志设置为 False，然后跳出循环。
12. 如果没有找到 NGF 元素，则打印当前元素 arr[i] 和 -1，以指示没有具有更高频率的 NGF 元素。
13. 从堆栈 s 中删除最后一个元素

解法 - 5 空间方法

我们可以使用空间高效的方法更有效地解决此问题。

让我们来理解以下步骤。

1. 创建一个名为“Pair”的类来存储整数对（元素、频率）。
2. 使用字典（HashMap）以对作为键，以它们的频率作为值，来有效地存储每个元素的频率。
3. 遍历输入数组，对于每个元素，将其频率存储在字典中。
4. 创建一个名为“res”的数组来存储最终输出。
5. 将“res”数组的最后一个元素初始化为 -1，因为输入数组的最后一个元素右侧没有元素，因此没有频率更高的元素。
6. 初始化一个空堆栈，用于跟踪元素及其频率。
7. 从最后一个元素开始，反向遍历输入数组。
8. 对于在数组中遇到的每个元素
   1. 将当前元素的频率与堆栈顶部元素的频率进行比较。
   2. 如果当前元素的频率更高，则从堆栈中弹出元素，并相应地在“res”数组中更新它们的 NGF 值。
   3. 继续此过程，直到不再满足频率条件或直到堆栈变空。
9. 如果弹出元素后堆栈变空，则意味着当前元素的右侧没有频率更高的元素。在这种情况下，将 -1 设置为当前元素在“res”数组中的下一个更高频率元素。
10. 如果处理后堆栈不为空，则意味着堆栈的顶部元素比当前元素具有更高的频率。将顶部元素的值设置为当前元素在“res”数组中的下一个更高频率元素。
11. 将当前元素及其频率一起推入堆栈。

这些步骤有效地查找并存储输入数组中每个元素的下一个更高频率 (NGF) 元素，为解决问题提供了一种清晰且简化的方法。

让我们来理解以下代码片段 -

示例 -

输出

[2, 2, 2, -1, -1, -1, -1, 3, -1, -1]

结论

在本教程中，我们探讨了在数组中查找下一个更高频率 (NGF) 元素的各种方法。我们介绍了朴素方法、高效的基于堆栈的解决方案以及空间高效的解决方案，提供了不同性能和内存需求的选项。