【剑指offer刷题笔记】39.数组中出现次数超过一半的数字

剑指No.39_数组中出现次数超过一半的数字

• 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
  可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例： 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

• 哈希表统计法：
  用一个哈希表记录每个数字和其出现次数的映射，一旦发现出现次数大于数组长度一半的情况，就返回那个数字。（空间和时间复杂度都为O（n））

public int majorityElementWay(int[] nums){
HashMap<Integer, Integer> map = new HashMap<>();
int length = nums.length;
int res = 0;
for (int i = 0; i < length; i++){
if (map.containsKey(nums[i])){
map.put(nums[i], map.get(nums[i]) + 1);
}else {
map.put(nums[i], 1);
}
if (map.get(nums[i]) > (length / 2)){
res = nums[i];
return res;
}
}
return res;
}

• 数组排序法：
  可知出现次数超过数组长度一半的数字，在数组排序之后一定出现在数组的中点，因此对数组进行排序之后取中点即可(空间复杂度为O(1)不需要额外空间，排序时时间复杂度略高)

• 摩尔投票法：
  基本原理是如果把众数作为+1票，其他数作为-1票，那么最后的总和一定>0。当遍历过程中出现=0的情况时，说明后面的数组中包含众数。从一开始就把当前数假定为众数，总和=0的话就再设下一个数为众数，直到遍历完之后最后假设的就是众数。

class Solution {
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;
}
}

最后

以上就是勤劳中心为你收集整理的【剑指offer刷题笔记】39.数组中出现次数超过一半的数字的全部内容，希望文章能够帮你解决【剑指offer刷题笔记】39.数组中出现次数超过一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。