Java 中数组中的多数元素

这是谷歌、亚马逊、TCS、Accenture 等顶级 IT 公司面试中经常出现的非常有趣的问题。通过解决这个问题，可以考察应聘者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将通过不同的方法和逻辑来探讨 **Java 数组中多数元素的查找**。我们还将创建相应的 Java 程序。

问题陈述

给定一个包含整数的数组。我们的任务是找到输入数组中出现次数最多的元素。

多数元素

多数元素是指出现次数大于输入数组大小一半的元素。

示例 1

输入

Int arr[] = {5, 1, 1, 1, 1, 1, 4, 9, 1, 0, 1, -2}

输出 1

解释：元素 1 出现的次数为 7，大于输入数组大小的一半，即 (12 / 2) = 6。

示例 2

输入

Int arr[] = {47, 8, 1, 6, 3, 6, 90, 52, 78, 47, 47, 47}

输出：输入数组中不存在多数元素。

解释：不存在出现次数大于输入数组大小一半的元素。

朴素方法

在此方法中，我们将使用两个嵌套循环。外层循环将从输入数组中选择一个元素（从左到右）。内层循环将计算外层循环选择的元素的出现次数。如果计数大于输入数组大小的一半，那么我们就找到了答案。如果没有，则考虑下一个迭代，依此类推。如果外层循环终止，则意味着输入数组中的所有元素都已被检查完毕，但未找到多数元素。

文件名：MajorityEle.java

输出

For the input array.
5 1 1 1 1 1 4 9 1 0 1 2 
The majority element is: 1


For the input array.
47 8 1 6 3 6 90 52 78 47 47 47 
The majority element is not found.

复杂度分析：该程序使用了嵌套循环。因此，程序的**时间复杂度**为 O(n²)，其中 n 是输入数组中元素的总数。程序的**空间复杂度**为 O(1)，因为程序不使用任何额外的空间。

方法：使用二叉搜索树

在此方法中，我们将逐个插入输入数组的元素，如果元素已存在于二叉搜索树中，则增加其计数。在任何阶段，如果任何节点的计数大于输入数组大小的一半，我们就找到了答案。

算法

观察以下算法。

步骤 1：构建一个 BST（二叉搜索树）；如果再次在 BST 中输入相同的元素，则该节点的出现次数会增加。

步骤 2：遍历输入数组并将元素放入 BST 中。

步骤 3：如果任何节点的最高出现次数大于输入数组大小的一半，则进行中序遍历以找到出现次数大于一半的节点。

步骤 4：否则，打印“不存在多数元素”的适当消息。

文件名：MajorityEle1.java

输出

For the input array.
5 1 1 1 1 1 4 9 1 0 1 2 
The majority element is: 1


For the input array.
47 8 1 6 3 6 90 52 78 47 47 47 
The majority element is not found.

复杂度分析：程序的**时间复杂度**与上一个程序相同。程序的**空间复杂度**为 O(n)，其中 n 是输入数组中元素的总数。空间复杂度是由于构建用于存储节点的二叉搜索树。

方法：使用排序

排序会将相同值的元素分组在一起。排序后，只需计算相同元素的计数，并检查其是否大于输入数组大小的一半。以下程序对此进行了说明。

文件名：MajorityEle2.java

输出

For the input array.
5 1 1 1 1 1 4 9 1 0 1 2 
The majority element is: 1


For the input array.
47 8 1 6 3 6 90 52 78 47 47 47 
The majority element is not found.

复杂度分析：由于程序使用了排序，因此程序的**时间复杂度**为 O(n * log(n))，其中 n 是输入数组中元素的总数。程序的**空间复杂度**为常数，即 O(1)。

方法：使用 HashMap

该方法非常直接。请观察以下步骤。

步骤 1：计算数组元素出现的频率。

步骤 2：将数组元素及其出现次数作为键值对存储在哈希映射中。

步骤 3：遍历哈希映射，检查元素的频率计数是否大于输入数组大小的一半。

步骤 4：显示输出。

请看下面的程序。

文件名：MajorityEle3.java

输出

For the input array.
5 1 1 1 1 1 4 9 1 0 1 2 
The majority element is: 1


For the input array.
47 8 1 6 3 6 90 52 78 47 47 47 
The majority element is not found.

复杂度分析：由于程序只使用了一个循环，因此程序的**时间复杂度**为 O(n)。该程序还使用了哈希映射。因此，程序的**空间复杂度**为 O(n)，其中 n 是输入数组中元素的总数。

方法：使用摩尔投票算法

请观察以下步骤。

步骤 1：遍历元素以维护多数元素的计数和索引，在本例中为 majIndex。

步骤 2：如果下一个元素与当前元素的值相同，则计数加 1。

步骤 3：如果下一个元素与当前元素的值不同，则计数减 1。

步骤 4：如果计数变为 0，则通过将当前元素的索引赋给 majIndex 来更新 majIndex，并将计数赋值为 1。

步骤 5：选择 majIndex 指向的元素，并查找该元素的出现次数。

步骤 6：如果计数大于输入数组大小的一半，则 majIndex 指向的元素是多数元素；否则，输入数组中不存在多数元素。

请看下面的程序。

文件名：MajorityEle4.java

输出

For the input array.
5 1 1 1 1 1 4 9 1 0 1 2 
The majority element is: 1


For the input array.
47 8 1 6 3 6 90 52 78 47 47 47 
The majority element is not found.

复杂度分析：程序的**时间复杂度**与上一个程序相同。由于程序不使用任何数据结构，因此**空间复杂度**为 O(1)。