Leetcode刷题100天—169. 多数元素(哈希表)—day10

- 日理万妓 2022-09-10 04:19 147阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210904153743521][]

#### [169. 多数元素][169.] ####

难度简单1114收藏分享切换为英文接收动态反馈

给定一个大小为 *n* 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 **大于** `⌊ n/2 ⌋` 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

**示例 1：**

输入：[3,2,3]
    输出：3

**示例 2：**

输入：[2,2,1,1,1,2,2]
    输出：2

**进阶：**

*  尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

package 哈希表;
    /* * 1 * https://leetcode-cn.com/problems/majority-element/ */
    
    import java.awt.print.Printable;
    import java.util.HashMap;
    import java.util.Map;
    
    //通过哈希表解决问题
    public class _169_多数元素 { 
    // 通过题目要求，我们可以使用哈希映射HashMap，存入key和value,如果有重复的key就加一
    	public static int majorityElement(int[] nums) { 
    		Map<Integer, Integer> counts=countNums(nums);
    // 声明的一个内部接口majorityEntry
    		Map.Entry<Integer, Integer> majorityEntry = null;
    		System.out.print(counts.entrySet());//[2=1, 3=2]
    // 通过for循环获取counts中一个个键值，然后作比较获取最大的那个键
            for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { 
                if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) { 
                    majorityEntry = entry;
                }
            }
    // 返回键
            return majorityEntry.getKey();
        }
    //
    	public static Map<Integer, Integer> countNums(int[] nums){ 
    // 设置哈希映射
    		Map<Integer, Integer> counts=new HashMap<Integer, Integer>();
    // 通过for循环遍历nums
    		for(int num:nums) { 
    			if (!counts.containsKey(num)) { 
    				counts.put(num, 1);
    			}else { 
    				counts.put(num, counts.get(num)+1);
    			}
    		}
    		return counts;
    	
    	}
    	public static void main(String args[]) { 
    		int nums[]=new int[3];
    		nums[0]=3;
    		nums[1]=2;
    		nums[2]=3;
    
    		int count=majorityElement(nums);
    		System.out.print(count);
    // return majorityEntry.getKey();
    
    	}
    	
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210904153743521]: /images/20220829/533e4f7c407a42159458c1665e9ddb7c.png
[169.]: https://leetcode-cn.com/problems/majority-element/