首页 > 基础资料 博客日记
剑指offer-28、数组中出现次数超过⼀半的数字
2025-09-09 09:30:02基础资料围观15次
Java资料网推荐剑指offer-28、数组中出现次数超过⼀半的数字这篇文章给大家,欢迎收藏Java资料网享受知识的乐趣
题⽬描述
数组中有⼀个数字出现的次数超过数组⻓度的⼀半,请找出这个数字。例如输⼊⼀个⻓度为 9 的数组 {1,2,3,2,2,2,5,4,2} 。由于数字 2 在数组中出现了 5 次,超过数组⻓度的⼀半,因此输出 2 。如果不存在则输出 0 。
思路及解答
哈希表法(HashMap)
哈希表法通过统计每个数字的出现次数来解决问题。遍历数组时,使用哈希表记录每个数字出现的次数,一旦发现某个数字的出现次数超过数组长度的一半,立即返回该数字。
public class Solution {
public int MoreThanHalfNum(int[] nums) {
// 创建哈希表,key为数字,value为出现次数
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
// 获取当前数字的出现次数并加1,若不存在则初始化为0再加1
int count = map.getOrDefault(num, 0) + 1;
// 若当前数字出现次数已超过数组长度一半,则返回该数字
if (count > nums.length / 2) {
return num;
}
map.put(num, count); // 更新哈希表
}
return 0; // 如果不存在多数元素,返回0(但题目假设总是存在)
}
}
- 时间复杂度:O(n),其中 n 是数组的长度。我们只需遍历数组一次。
- 空间复杂度:O(n),最坏情况下需要存储所有不同的数字。
排序法
排序法的思路非常巧妙:由于多数元素的数量超过数组长度的一半,那么将数组排序后,中间位置的元素一定是多数元素。
public class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums); // 对数组进行排序
return nums[nums.length / 2]; // 返回中间位置的元素
}
}
摩尔投票法(Boyer-Moore Voting Algorithm)
- 如果使⽤ hashmap 直接统计,需要额外的空间,我们不希望使⽤额外空间;
- 如果使⽤排序之后再统计,需要时间复杂度为O(nlogn), 我们希望时间复杂度更低⼀点。
摩尔投票法是一种高效且空间复杂度低的算法。其核心思想是通过票数的抵消来找出多数元素。算法维护一个候选众数 candidate
和其票数 count
。遍历数组时,若 count
为0,则选择当前数字作为候选;若当前数字与候选相同,则票数加1,否则减1。由于多数元素的存在,最终剩下的候选一定是多数元素。
public class Solution {
public int majorityElement(int[] nums) {
int candidate = 0; // 候选众数
int count = 0; // 票数统计
for (int num : nums) {
if (count == 0) { // 如果票数为0,选择当前数字作为候选
candidate = num;
}
// 如果当前数字与候选相同,则票数加1,否则减1
count += (num == candidate) ? 1 : -1;
}
// 可选:验证candidate是否真的是多数元素(根据题目假设,通常不需要)
// 但如果题目要求不存在多数元素时返回0,则需要验证步骤
count = 0;
for (int num : nums) {
if (num == candidate) count++;
}
return count > nums.length / 2 ? candidate : 0;
}
}
- 时间复杂度:O(n),只需遍历数组两次(一次投票,一次验证)。
- 空间复杂度:O(1),只使用了常数个额外变量
文章来源:https://www.cnblogs.com/seven97-top/p/19076699
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签: