网站首页模板怎么做策划,桂林市教科所,珠海建设网站首页,猎头用什么网站做单【问题描述】[简单]
数组中有一个数字出现的次数超过数组长度的一半#xff0c;请找出这个数字。你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2限制#xff1a;1 数组长度 50000【解答思…【问题描述】[简单]
数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2限制1 数组长度 50000
【解答思路】
1. 哈希表统计法
哈希表统计法 遍历数组 nums 用 HashMap 统计各数字的数量最终超过数组长度一半的数字则为众数。此方法时间和空间复杂度均为 O(N)O(N) 。 时间复杂度O(N) 空间复杂度O(N
public int majorityElement(int[] nums) {int n nums.length;int max 1 ;int ans nums[0];HashMapInteger, Integer mapnew HashMapInteger, Integer();for(int num :nums){if(map.containsKey(num)){map.put(num,map.get(num)1);}else{map.put(num,1);}}for(int num: map.keySet()){if(map.get(num) max){max map.get(num) ;ans num;}}return ans;}HashMapInteger, Integer map new HashMap();for (int num : nums) {if (map.containsKey(num)) {map.put(num, map.getOrDefault(num, 0) 1);} else {map.put(num, 1);}if (map.get(num) nums.length / 2) {return num;}}return 0;
}2. 摩尔投票法 最佳
核心理念为 “正负抵消” 时间复杂度O(N) 空间复杂度O(1) public int majorityElement(int[] nums) {int x 0, votes 0;for(int num : nums){if(votes 0) x num;votes num x ? 1 : -1;}return x;} 3. 数组排序法
将数组 nums 排序由于众数的数量超过数组长度一半因此 数组中点的元素 一定为众数。 时间复杂度O(NlogN) 空间复杂度O(1) public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}【总结】
1.Java中HashMap遍历几种方式 2.HashMap常用语法
1.import java.util.HashMap;//导入;
2.HashMapK, V mapnew HashMapK, V();//定义mapK和V是类不允许基本类型;
3.void clear();//清空
4.put(K,V);//设置K键的值为V
5.V get(K);//获取K键的值
6.boolean isEmpty();//判空
7.int size();//获取map的大小
8.V remove(K);//删除K键的值返回的是V可以不接收
9.boolean containsKey(K);//判断是否有K键的值
10.boolean containsValue(V);//判断是否有值是V
11.Object clone();//浅克隆类型需要强转如HashMapString , Integer map2(HashMapString, Integer) map.clone();
3. 一题多解 熟悉掌握一种 其他掌握思想
转载链接https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/ 参考链接https://blog.csdn.net/gary0917/article/details/79783713 参考链接https://www.cnblogs.com/shoulinniao/p/11966194.html
