网站seo监测,线上商城介绍,北京建网站需要多少钱,百度最新秒收录方法2022题目#xff1a;
数组中有一个数字出现的次数超过数组长度的一半#xff0c;请找出这个数字。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例#xff1a; 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 思考#xff1a; 方法一#xff1a;投…题目
数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 思考 方法一投机取巧 将数组排序出现次数超过一半的数字肯定在数组中间的那个位置
题解
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}思考 方法二哈希表辅助 使用一个 mapkey 存数组中的数字val 存出现的次数 当有数字出现次数超过数组长度一半时直接返回
题解
class Solution {public int majorityElement(int[] nums) {MapInteger,Integer map new HashMap();for(int num : nums){map.put(num,map.getOrDefault(num,0)1);if(map.get(num) nums.length1) return num;}return 0;}
}思考 方法三摩尔投票法 众数和非众数投票初始票数为 0为 0 时假设当前数字为众数 遍历数组是众数 1不是众数 -1为 0 就接着继续重新来 最后得到众数
题解
class Solution {public int majorityElement(int[] nums) {int vote 0;int x 0;for (int i 0; i nums.length; i) {if (vote 0) x nums[i];if (x nums[i]) vote;else vote--;}return x;}
}
