首页 > 代码库 > 169. Majority Element

169. Majority Element

2024-09-01 00:58:11   218人阅读

Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.

You may assume that the array is non-empty and the majority element always exist in the array.

题目大意

给定size 为n的数组，查找出主元素，就是出现次数大于n/2次的元素。你可以假定数组非空，而且主元素一定存在。

解题思路：
（1）使用HashMap，Map的特点：不允许重复元素，因此在存储前需要判断是否存在
（2）判断HashMap中存在nums[i],如果存在，使用hm.get(nums[i])获取value，即通过key来获得value值，即count(出现的次数)
（3）如果count大于数组长度的一般，即返回该元素
（4）如果count不满足条件，向HashMap存储元素以及出现的次数。

 1  /* Map的特点：不允许重复元素，因此在存储前需要判断是否存在         */    
 2          Map<Integer, Integer> hm=new HashMap<Integer, Integer>();        
 3          for (int i = 0; i < nums.length; i++)        
 4          {            
 5              int count=0;            
 6              //判断HashMap中存在nums[i],如果存在，使用hm.get(nums[i])获取value            
 7              //即通过key来获得value值，即count(出现的次数)        
 8              if (hm.containsKey(nums[i]))            
 9              {                
10                  count=hm.get(nums[i])+1;            
11                  
12              }            
13              else            
14              {                
15                  count=1;            
16                  
17              }            
18              //如果count大于数组长度的一般，即返回该元素            
19              if (count>nums.length/2)            
20              {                
21                  return nums[i];        
22                  }            
23                  //向HashMap存储元素以及出现的次数        
24                  hm.put(nums[i], count);    
25                  }        
26                  return 0;

169. Majority Element


联系
我们