给定一个大小为n的数组nums,返回其中的多数元素。多数元素是指在数组中出现次数大于Ln/2]的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素Java代码
时间: 2024-08-13 20:05:06 浏览: 86
这是一个经典的计算机科学问题,通常使用哈希表或“三数取中”(Ternary Search)方法来解决。这里,我将给出一个基于哈希表的Java解决方案:
```java
import java.util.HashMap;
import java.util.Map;
public class MajorityElement {
public int majorityElement(int[] nums) {
// 创建一个HashMap来存储每个元素及其出现次数
Map<Integer, Integer> countMap = new HashMap<>();
// 遍历数组
for (int num : nums) {
// 如果元素已经在地图中,增加计数
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
// 如果元素的计数超过n/2,我们找到了多数元素,直接返回
if (countMap.get(num) > nums.length / 2) {
return num;
}
}
// 如果遍历完整个数组都没有找到多数元素,返回任何一个出现次数最多的元素(如果有多个)
return countMap.keySet().stream()
.filter(mapEntry -> mapEntry.getValue() == nums.length / 2)
.findFirst().orElseThrow(() -> new IllegalArgumentException("No majority element found"));
}
}
```
在这个代码中,我们遍历数组`nums`,对于每个元素,如果它不在`countMap`中,就添加并初始化计数为1。如果已经存在,就将其计数加1。一旦发现某个元素的计数超过数组长度的一半,我们立即返回该元素作为多数元素。如果遍历结束仍未找到,则说明没有出现次数超过一半的元素,返回任何一个出现次数等于数组长度一半的元素。
阅读全文