3
#yyds干货盘点# 解决剑指offer：数组中出现次数超过一半的数字
source link: https://blog.51cto.com/u_15488507/5283397
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 解决剑指offer：数组中出现次数超过一半的数字
原创1.简述：
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：，数组中元素的值
要求：空间复杂度：，时间复杂度
输入描述：
保证数组输入非空，且保证有解
[1,2,3,2,2,2,5,4,2]
[3,3,3,3,2,2,2]
2.代码实现：
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
//哈希表统计每个数字出现的次数
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
//遍历数组
for(int i = 0; i < array.length; i++){
//统计频率
if(!mp.containsKey(array[i]))
mp.put(array[i], 1);
else
mp.put(array[i], mp.get(array[i]) + 1);
//一旦有个数大于长度一半的情况即可返回
if(mp.get(array[i]) > array.length / 2)
return array[i];
}
return 0;
}
}
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
//哈希表统计每个数字出现的次数
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
//遍历数组
for(int i = 0; i < array.length; i++){
//统计频率
if(!mp.containsKey(array[i]))
mp.put(array[i], 1);
else
mp.put(array[i], mp.get(array[i]) + 1);
//一旦有个数大于长度一半的情况即可返回
if(mp.get(array[i]) > array.length / 2)
return array[i];
}
return 0;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK