Finding the Majority Element of an Array in Java – 用 Java 查找数组中的多数元素

最后修改: 2024年 3月 14日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.导言

In this tutorial, we’ll explore different approaches to finding the majority element within an array. For each approach, we’ll provide their respective code implementations and analysis of time and space complexities.

在本教程中，我们将探讨在 数组中查找多数元素的不同方法。对于每种方法，我们都将提供各自的代码实现以及时间和空间复杂性分析。

2. Problem Statement

2 问题陈述

Let’s understand the problem of finding the majority element in an array. We’re given an array of integers and our objective is to determine if a majority element exists within it.

让我们来了解一下寻找数组中多数元素的问题。我们给定了一个整数数组，目的是确定其中是否存在多数元素。

A majority element appears more frequently than any other element, surpassing the threshold of occurring more than n/2 times in the array, where n represents the array’s length. This means identifying the element that dominates the array in terms of occurrence frequency.

多数元素比其他元素出现得更频繁，超过了在数组中出现 n/2 次的临界值，其中 n 代表数组的长度。

Before delving into each approach, we’ll utilize the provided sample data as input:

在深入研究每种方法之前，我们将利用提供的样本数据作为输入：

int[] nums = {2, 3, 2, 4, 2, 5, 2};

3. Using a for Loop

3.使用 for 循环

One straightforward approach to finding the majority element involves iterating through the array with a for loop. This approach involves iterating through the array using a for loop and maintaining a count of occurrences for each element. We’ll then check if any element satisfies the majority condition, meaning it appears in more than half the slots of the array.

查找多数元素的一种直接方法是使用 for 循环遍历数组。这种方法是使用 for 循环遍历数组，并对每个元素的出现次数进行计数。然后，我们将检查是否有元素满足多数条件，即它出现在数组一半以上的插槽中。

3.1. Implementation

3.1 实施

In this implementation, we iterate through the array using a for loop. For each element in the array, we initialize a count variable to keep track of its occurrences. Subsequently, we iterate through the array again to count the occurrences of the current element.

在此实现中，我们使用 for 循环遍历数组。对于数组中的每个元素，我们都会初始化一个 count 变量，以跟踪其出现次数。随后，我们再次遍历数组，计算当前元素的出现次数。

As we iterate through the array, if we encounter a majority element with a count greater than n/2, we can immediately return the element:

当我们遍历数组时，如果遇到计数大于 n/2 的多数元素，我们可以立即返回该元素：

int majorityThreshold = nums.length / 2;
Integer majorityElement = null;

for (int i = 0; i < nums.length; i++) {
    int count = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[i] == nums[j]) {
            count++;
        }
    }
    if (count > majorityThreshold) {
        majorityElement = nums[i];
        break;
    }
}

assertEquals(2, majorityElement);

3.2. Complexity Analysis

3.2.复杂性分析

The time complexity of the for-loop approach is O(n^2). This quadratic time complexity arises due to the nested loops utilized in the implementation, where each element in the array is compared against every other element. On the other hand, the space complexity is O(1).

for循环方法的时间复杂度为O(n^2)。这种二次方时间复杂度的产生是由于在实现过程中使用了嵌套循环，在这种循环中，数组中的每个元素都要与其他元素进行比较。

While the approach is simple to implement and has minimal space overhead, it’s not the most efficient for large arrays due to its quadratic time complexity.

虽然这种方法实现起来很简单，空间开销也很小，但由于其二次方时间复杂性，对于大型阵列来说并不是最有效的。

4. Using a Sorting Approach

4.使用分类方法

In this approach, we leverage a sorting algorithm to efficiently identify the majority element in an array. The strategy involves sorting the array in ascending order, which enables us to identify consecutive occurrences of elements.

在这种方法中，我们利用排序算法来有效识别数组中的多数元素。该策略包括按升序对数组进行排序，这使我们能够识别连续出现的元素。

Given that a majority element appears more than half the size of the array, after sorting, it will either occupy the middle index (if the array length is odd) or be next adjacent to the middle elements (if the array length is even). Consequently, by examining the middle elements of the sorted array, we can ascertain whether one of them qualifies as the majority element.

如果多数元素的大小超过数组大小的一半，那么在排序后，它要么会占据中间索引（如果数组长度为奇数），要么会紧邻中间元素（如果数组长度为偶数）。因此，通过检查已排序数组的中间元素，我们可以确定其中一个元素是否符合多数元素的条件。

4.1. Implementation

4.1.实施

First, we use Arrays.sort() to sort the array in ascending order. This step is crucial as it enables us to identify consecutive occurrences of elements more easily. Next, we iterate through the sorted array and keep track of the middle element’s occurrence count. Inside the loop, we also check if the count is greater than half the size of the array.

首先，我们使用 Arrays.sort() 对数组进行升序排序。这一步至关重要，因为它能让我们更轻松地识别元素的连续出现。接下来，我们遍历排序后的数组，并跟踪中间元素的出现次数。在循环中，我们还会检查计数是否大于数组大小的一半。

If it is, it means the current element has appeared more than half the time, and it’s identified as the majority element. The code then returns this element. Let’s demonstrate this concept using a code snippet:

如果是，则表示当前元素出现的时间超过一半，并被识别为多数元素。代码就会返回该元素。让我们用一段代码来演示这个概念：

Arrays.sort(nums);
int majorityThreshold = nums.length / 2;
int count = 0;
Integer majorityElement = null;
for (int i = 0; i < nums.length; i++) {
    if (nums[i] == nums[majorityThreshold]) {
        count++;
    }

    if (count > majorityThreshold) {
        majorityElement = nums[majorityThreshold];
        break;
    }
}

assertEquals(2, majorityElement);

4.2. Complexity Analysis

4.2.复杂性分析

The time complexity of this approach is typically O(n log n) due to sorting, and the space complexity is O(1) as it uses constant extra space. This approach is slightly more efficient compared to the for-loop approach, but it might not be the most optimal solution for very large arrays due to the sorting operation’s time.

由于需要进行排序，这种方法的时间复杂度通常为O(n log n) ，而空间复杂度为O(1)，因为它使用了恒定的额外空间。与for循环方法相比，这种方法的效率略高，但由于排序操作需要时间，对于超大型数组来说，它可能不是最佳解决方案。

5. Using HashMap

5.使用 HashMap

This approach uses a HashMap to store the frequency of each element in the array.

这种方法使用 HashMap 来存储数组中每个元素的频率。

5.1. Implementation

5.1.实施

In this approach, we iterate through the array, incrementing the count of each element we encounter in the HashMap. Finally, we iterate through the HashMap and check if any element’s count is greater than half the size of the array. If a majority element is found, we return it; otherwise, we return -1 to indicate that no majority element exists in the array.

在这种方法中，我们遍历数组，递增 HashMap 中遇到的每个元素的计数。最后，我们遍历 HashMap 并检查是否有元素的计数大于数组大小的一半。如果找到多数元素，我们将返回它；否则，我们将返回 -1 表示数组中不存在多数元素。

Here’s an example implementation:

下面是一个实施示例：

Map<Integer, Integer> frequencyMap = new HashMap<>();
Integer majorityElement = null;

for (int num : nums) {
    frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}

int majorityThreshold = nums.length / 2;
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
    if (entry.getValue() > majorityThreshold) {
        majorityElement = entry.getKey();
        break;
    }
}

assertEquals(2, majorityElement);

5.2. Complexity Analysis

5.2.复杂性分析

Overall, using a HashMap is a more efficient approach, especially for larger datasets, due to its linear time complexity. It has a time complexity of O(n) due to iterating through the array once and iterating through the HashMap once.

总的来说，使用 HashMap 是一种更高效的方法，尤其是对于较大的数据集，因为它具有线性时间复杂性。由于要迭代一次数组和迭代一次 HashMap ，因此时间复杂性为 O(n) 。

However, this approach requires additional space for HashMap, which can be a concern for memory-constrained environments. In the worst-case scenario, the space complexity will be O(n) as the HashMap might store all unique elements in the array.

然而，这种方法需要为 HashMap 分配额外的空间，这可能是内存受限环境的一个问题。在最坏的情况下，空间复杂度将达到 O(n)，因为 HashMap 可能会存储数组中所有唯一的元素。

6. Using the Boyer-Moore Voting Algorithm

6.使用博耶-摩尔投票算法

This algorithm is popularly used to find the majority element in a sequence of elements using linear time complexity and a fixed amount of memory.

这种算法常用于利用线性时间复杂度和固定的内存量来查找元素序列中的多数元素。

6.1. Implementation

6.1.实施

In the initialization step, we create two variables: a candidate element and a count. The candidate element is set to the first element in the array, and the count is set to 1.

在初始化步骤中，我们创建了两个变量：候选元素和计数。候选元素设置为数组中的第一个元素，计数设置为 1。

Next, in the iteration step, we loop through the remaining elements in the array. For each subsequent element, we increment the count if the current element is the same as the candidate element. This signifies that this element also potentially contributes to being the majority. Otherwise, we decrease the count. This counteracts the previous votes for the candidate.

接下来，在迭代步骤中，我们循环遍历数组中的剩余元素。对于后面的每个元素，如果当前元素与候选元素相同，我们就增加计数。这意味着该元素也有可能成为多数元素。否则，我们就减少计数。这样就抵消了之前对候选人的投票。

If the count reaches 0, the candidate element is reset to the current element, and the count is set back to 1. This is because if previous elements cancel each other out, the current element might be a new contender for the majority.

如果计数达到 0，候选元素就会重置为当前元素，计数也会设回 1。这是因为如果之前的元素相互抵消，当前元素可能会成为多数元素的新竞争者。

After iterating through the entire array, we verify by iterating through the array again and counting the occurrences of the candidate element. If the candidate appears more than n/2 times, we return it as the majority element. Otherwise, we return -1.

在遍历整个数组后，我们再次遍历数组并计算候选元素的出现次数，以此进行验证。如果候选元素出现的次数超过 n/2，我们就将其作为多数元素返回。否则，我们将返回-1。

Let’s proceed with the implementation:

让我们继续实施：

int majorityThreshold = nums.length / 2;
int candidate = nums[0];
int count = 1;
int majorityElement = -1;

for (int i = 1; i < nums.length; i++) {
    if (count == 0) {
        candidate = nums[i];
        count = 1;
    } else if (candidate == nums[i]) {
        count++;
    } else {
        count--;
    }
}

count = 0;
for (int num : nums) {
    if (num == candidate) {
        count++;
    }
}

majorityElement = count > majorityThreshold ? candidate : -1;
assertEquals(2, majorityElement);

Here is the breakdown of the iteration step:

下面是迭代步骤的细目：

Initial stage: [Candidate (2), Count (1)]
Iteration 1: [Candidate (2), Count (0), Element (3)] // "3" != candidate, count--
Iteration 2: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++
Iteration 3: [Candidate (2), Count (0), Element (4)] // "4" != candidate, count--
Iteration 4: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++
Iteration 5: [Candidate (2), Count (0), Element (5)] // "5" != candidate, count--
Iteration 6: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++

6.2. Complexity Analysis

6.2.复杂性分析

This algorithm has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for finding the majority element in an array.

该算法的时间复杂度为O(n)，空间复杂度为O(1)，因此是查找数组中多数元素的高效解决方案。

7. Summary

7.摘要

This table summarizes the time and space complexities of each approach as well as their advantages. It provides a quick overview of the trade-offs and benefits of each approach.

本表总结了每种方法在时间和空间上的复杂性及其优势。它提供了每种方法的权衡和优势的快速概览。

Approach Time Complexity Space Complexity Pros & Cons
For loop O(n^2) O(1) – Straightforward to implement
– Requires minimal additional space
– Inefficient for large arrays due to nested loops
Sorting O(n log n) O(1) or O(n) – Simple implementation
– No additional space overhead if in-place sorting is used
– Introduces additional time complexity due to sorting
HashMap O(n) O(n) – Linear time complexity for both processing and space usage
– Efficiently handles large arrays
– Requires additional space for HashMap storage
Boyer-Moore Voting O(n) O(1) – Optimal time and space complexity
– Efficient for large arrays

8. Conclusion

8.结论

In this article, we explored various approaches to finding the majority element in an array.

在本文中，我们探讨了寻找数组中多数元素的各种方法。

The for-loop approach provides a simple implementation but is inefficient for large arrays due to its nested loops. The HashMap approach provides linear time complexity and efficiently handles large arrays, but it requires additional space for HashMap storage.

for循环方法提供了一种简单的实现方法，但由于其嵌套循环，对于大型数组来说效率不高。HashMap 方法具有线性时间复杂性，可高效处理大型数组，但需要额外的空间用于 HashMap 存储。

Finally, the Boyer-Moore Voting Algorithm offers optimal time and space complexity and is efficient for large arrays.

最后，Boyer-Moore 投票算法具有最佳的时间和空间复杂性，对大型阵列也很有效。

As always, the source code for the examples is available over on GitHub.

与往常一样，这些示例的源代码可在 GitHub 上获取。