主要元素
难度:
标签:
题目描述
A majority element is an element that makes up more than half of the items in an array. Given a integers array, find the majority element. If there is no majority element, return -1. Do this in O(N) time and O(1) space.
Example 1:
Input: [1,2,5,9,5,9,5,5,5] Output: 5
Example 2:
Input: [3,2] Output: -1
Example 3:
Input: [2,2,1,1,1,2,2] Output: 2
代码结果
运行时间: 28 ms, 内存: 17.6 MB
/*
* 思路：虽然 Java Stream API 不适用于所有 O(1) 空间复杂度的场景，但我们可以通过转换为基本数组操作来使用流。
* 这里我们依然使用摩尔投票算法，但将其包装在流中处理。
*/
import java.util.stream.IntStream;
public class MainElementFinderStream {
public int findMajorityElement(int[] nums) {
// 第一步：找到候选元素
int[] candidateAndCount = IntStream.of(nums).collect(() -> new int[]{0, 0}, (acc, num) -> {
if (acc[1] == 0) {
acc[0] = num;
}
acc[1] += (num == acc[0]) ? 1 : -1;
}, (acc1, acc2) -> {});
int candidate = candidateAndCount[0];
// 第二步：验证候选元素是否为主要元素
long count = IntStream.of(nums).filter(num -> num == candidate).count();
return count > nums.length / 2 ? candidate : -1;
}
public static void main(String[] args) {
MainElementFinderStream finder = new MainElementFinderStream();
int[] nums1 = {1, 2, 5, 9, 5, 9, 5, 5, 5};
int[] nums2 = {3, 2};
int[] nums3 = {2, 2, 1, 1, 1, 2, 2};
System.out.println(finder.findMajorityElement(nums1)); // 输出 5
System.out.println(finder.findMajorityElement(nums2)); // 输出 -1
System.out.println(finder.findMajorityElement(nums3)); // 输出 2
}
}解释
方法:
这个题解采用了摩尔投票算法（Boyer-Moore Voting Algorithm），用于找出数组中的主要元素。算法的基本思路是维护一个候选主要元素和一个计数器。遍历数组时，若计数器为零，则将当前元素设置为候选元素，并将计数器设为1。如果计数器不为零，当遇到与候选元素相同的数时，计数器加1；否则，计数器减1。这样，遍历结束后，候选元素可能是主要元素。然而，由于计数器的减少可能导致非主要元素成为候选，因此需要再次遍历数组来确认候选元素的出现次数是否真的超过了数组长度的一半。若是，则返回该元素；若不是，则返回-1。
时间复杂度:
O(N)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在摩尔投票算法中，遇到与候选元素不同的元素时，计数器需要减1？
▷🦆
在算法的第二次遍历中，是如何确认候选元素是否真的是主要元素的？
▷🦆
如果数组中的元素都不相同，摩尔投票算法的候选元素会是怎样的？
▷