Java 中 K 个最频繁元素

给定一个整数数组。还给了一个数字 K。我们的任务是找出给定整数数组中 K 个最频繁的元素。

示例：1

输入

Int arr[] = {5, 5, 3, 7, 9, 7, 0, 1, 2, 7}, int k = 2

输出 {5, 7}

解释：出现次数最多的前两个元素是 7（3 次）和 5（2 次）。输出显示了相同的内容。

示例：2

输入

Int arr[] = {9, 2, 0, 1, 4, 8, 6, 3, 0, 1, 5, 4, 4, 1, 7}, int k = 3

输出 {0, 1, 4}

解释：出现次数最多的前三个元素是 0（2 次）、1（3 次）和 4（3 次）。输出显示了相同的内容。

方法：使用部分排序

在这种方法中，我们将问题分解成更小的问题。显然，第 K 个最频繁的元素是（n - K）个最不频繁的元素。因此，我们对从最不频繁的元素到最频繁的元素进行部分排序，直到第（n - K）个最不频繁的元素占据排序数组中的第（n - K）个位置。我们通过快速选择来实现这一点。请注意以下步骤。

步骤 1：创建一个哈希映射，其中键是元素，值是该元素在输入数组中出现的频率。

步骤 2：使用循环遍历元素，并在上一步创建的哈希映射中将其值加 1。

步骤 3：将 len 设置为“MAP.SIZE”。

步骤 4：创建一个名为 temp 的数组，其中将包含整数，并将哈希映射的所有键插入其中。

步骤 5：调用方法 quickSel(0, 'len' - 1, len - 'K')。

步骤 6：返回数组 temp 中从索引 (len - K) 到 len 的元素。

在方法 quickSel(lft, rght, kSml') 中，执行以下操作：

• 如果“lft”与“rght”相同，则退出方法。
• 选择一个位于“lft”和“rght”之间的枢轴。
• 将枢轴设置为 partition(lft, rght, pvt)。
• 如果 'kSml' 与 'pvt' 相同，则退出方法。
• 否则，如果 'kSml' 小于 'pvt，则在左分区上调用 quickselect() 方法。否则，在右分区上调用 quickSel() 方法。

观察基于上述步骤的以下实现。

文件名： KMostFreq.java

输出

For the input array: 
5 5 3 7 9 7 0 1 2 7 
The first 2 frequent elements are:
5 7 

For the input array: 
9 2 0 1 4 8 6 3 0 1 5 4 4 1 7 
The first 3 frequent elements are:
0 1 4

复杂度分析：在最坏的情况下，枢轴不会将问题平分。因此，时间复杂度为 O(n2)。但是，在大多数情况下，这种情况的可能性很小。因此，程序的平均时间复杂度为 O(n)。由于使用了哈希映射，因此程序的空间复杂度为 O(n)，其中 n 是输入数组中存在的元素总数。

方法：使用堆

我们将根据元素在数组中出现的次数对数组进行排序。我们将使用一个哈希映射，其中键是元素本身，值是元素在输入数组中出现的次数。然后，我们将使用堆根据元素出现的次数以降序对输入数组的元素进行排序。涉及的步骤如下所述。

步骤 1：如果 K 的值等于输入数组的大小，则返回输入数组。

步骤 2：创建一个哈希映射，其中键是元素，值是该元素在输入数组中出现的频率。

步骤 3：使用循环遍历元素，并在上一步创建的哈希映射中将其值加 1。

步骤 4：创建一个优先队列 pq，以便按元素频率的降序对将要排序的元素进行排序。

步骤 5：将所有键添加到映射中，然后添加到堆中。

步骤 6：创建一个数组 temp[] 用于存储答案

步骤 7：将堆的前 k 个元素添加到数组 temp 中，然后返回数组 temp。

以下实现使用了上述步骤。

文件名： KMostFreq1.java

输出

For the input array: 
5 5 3 7 9 7 0 1 2 7 
The first 2 frequent elements are:
7 5 

For the input array: 
9 2 0 1 4 8 6 3 0 1 5 4 4 1 7 
The first 3 frequent elements are:
1 4 0

复杂度分析：创建哈希映射需要 O(N) 时间，在最坏的情况下，构建堆需要 O(n x log(n)) 时间，因为向堆添加元素需要 log(n) 时间。因此，程序的总时间复杂度为 O(n x log(n))，其中 n 是输入数组中存在的元素总数。程序的空间复杂度与上一个程序相同。

让我们进一步优化以降低时间复杂度。

方法：使用桶排序

显然，一个元素在输入数组中最多可以出现 n 次，最少可以出现 1 次。因此，我们可以创建 n 个桶，并将元素根据它们出现的频率放入桶中。例如，如果一个数字出现 t 次，那么它将进入 bucketArr[t] 桶。将所有元素放入桶后，从最右侧桶开始的 k 个元素就是我们的解决方案。

算法

步骤 1：创建一个哈希映射，其中键是元素，值是该元素在输入数组中出现的频率。

步骤 2：使用循环遍历元素，并在上一步创建的哈希映射中将其值加 1。

步骤 3：创建一个名为 bucketArr[] 的数组。

步骤 4：根据其出现频率将哈希映射的所有键添加到 bucketArr[] 中。

步骤 5：创建一个 temp[] 数组用于存储答案。

步骤 6：从最右侧的桶开始，将 'K' 个元素添加到 temp[] 数组中。

步骤 7：返回数组 temp。

文件名： KMostFreq2.java

输出

For the input array: 
5 5 3 7 9 7 0 1 2 7 
The first 2 frequent elements are:
7 5 

For the input array: 
9 2 0 1 4 8 6 3 0 1 5 4 4 1 7 
The first 3 frequent elements are:
1 4 0

复杂度分析：该程序仅在特定时间段内遍历输入数组。因此，程序的时​​间复杂度为 O(n)，其中 n 是数组中存在的元素总数。程序的空间复杂度与上一个程序相同。