Java Program to Find the Frequency of All Duplicate Elements in an Array

此 Java 程序查找并显示数组中所有重复元素的频率。通过使用 HashMap，该程序可以有效地计算每个组件的出现次数。然后，它会识别并输出出现次数超过一次的元素，有助于理解数据分布和识别数组中的重复项。

示例 1

输入: arr[] = {1, 2, 3, 2, 1, 4, 1}

输出: 以下是重复元素的频率 -

1 -> 3

2 -> 2

示例 2

输入: arr[] = {9, 8, 8, 7, 9, 7, 7}

输出: 以下是重复元素的频率 -

7 -> 3

8 -> 2

9 -> 2

方法：使用 HashMap

代码中采用的方法是基于 HashMap 的方法，该方法可以有效地计算数组中元素的频率。它利用 HashMap 来存储和更新计数，然后根据其频率过滤和显示重复项。

算法

步骤 1: 创建一个空的 HashMap 来存储 数组 中每个元素的频率。

步骤 2: 遍历数组中的每个元素并更新其在 HashMap 中的计数。如果该组件尚未存在，则将其计数初始化为 1。

步骤 3: HashMap 填充完毕后，准备识别和显示重复元素。

步骤 4: 遍历 HashMap 中的条目，并检查每个元素的频率是否大于 1，这表示存在重复项。

步骤 5: 打印重复的元素及其频率。

让我们在 Java 程序中实现上述步骤。

文件名：DuplicateFrequency.java

输出

 
Duplicate elements and their frequencies:
Element: 4, Frequency: 3
Element: 6, Frequency: 2
Element: 8, Frequency: 2   

时间复杂度: 时间复杂度为 O(n * log(n))，这是对数组进行排序并为每个唯一元素执行二分查找的结果。

辅助空间: 辅助空间复杂度为 O(n)，因为使用了与输入大小成比例的额外空间。

方法：排序和二分查找

基于 排序 和 二分 查找的方法首先对数组进行排序，以便对重复元素进行分组，从而更容易识别它们。然后使用二分查找有效地查找每个组件的第一个和最后一个出现位置，从而能够快速计算频率。

算法

步骤 1: 首先对输入数组进行排序，将重复的元素分组在一起。

步骤 2: 将索引 i 设置为 0，开始遍历排序后的数组。

步骤 3: 在遍历数组时，使用二分查找来查找每个元素的第一个和最后一个出现位置，并计算其频率。

步骤 4: 如果元素的频率大于 1，则打印该元素及其频率，并将索引 i 移动以跳过其所有出现。

步骤 5: 如果当前元素没有重复项，则将索引 i 加 1 以处理下一个唯一组件。

让我们在 Java 程序中实现上述步骤。

文件名：DuplicateFrequencyOptimized.java

输出

 
Duplicate elements and their frequencies:
Element: 4, Frequency: 3
Element: 6, Frequency: 2
Element: 8, Frequency: 2   

时间复杂度: 时间复杂度为 O(n * log2(n))，这是对数组进行排序并为每个唯一元素执行二分查找所致。

辅助空间复杂度: 辅助空间复杂度为 O(1)，因为它除了输入数组之外，只使用了常量级别的额外空间。