Java解决多数元素
01 题目
-
给定一个大小为
n
的数组nums
,返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋
的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:nums = [3,2,3] 输出:3
示例 2:
输入:nums = [2,2,1,1,1,2,2] 输出:2
提示:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
02 知识点
- 循环
- map
- 动态规划
03 我的题解思路
public class majorityElement {
public static void main(String[] args) {
// 测试数据
int[] nums= {2,2,1,1,1,2,2};
System.out.println(majorityElement1(nums));
}
public static int majorityElement1(int[] nums) {
int n=nums.length/2;//用于比较多数元素
Map<Integer,Integer> map=new HashMap<Integer, Integer>();//用于统计每个数出现个数
for (int i = 0; i < nums.length; i++) {//循环整个数组
// 没找到就赋初始值,找到就值加1
Integer num=map.get(nums[i]);
if(num!=null) {
num++;
map.put(nums[i], num);
}else{
map.put(nums[i], 1);
}
}
// 再次循环数组,返回唯一多数元素
for (int i : nums) {
if(map.get(i)>n) {
return i;
}
}
return 0;
}
}