面试题 17.10. 主要元素 (摩尔投票法）

方法一：Map方法（不满足题目空间复杂度）方法二：摩尔投票法

面试题 17.10. 主要元素 题目链接：https://leetcode-cn.com/problems/find-majority-element-lcci/

方法一：Map方法（不满足题目空间复杂度）

class Solution { public int majorityElement(int[] nums) { Map<Integer,Integer> map=new HashMap<>(); int len=nums.length; int find=-1; for (int tmp: nums) { map.put(tmp,map.getOrDefault(tmp,0)+1); if (map.get(tmp)>len/2){ find=tmp; System.out.println(find); } } return find; } }

方法二：摩尔投票法

学习链接：https://www.zhihu.com/question/49973163

class Solution { public int majorityElement(int[] nums) { int tmp=nums[0]; int count=1; for (int i = 1; i <nums.length ; i++) { if (nums[i]==tmp){ count++; }else { count--; } if (count==0){ tmp=nums[i]; count=1; } } int num=0; for (int w:nums){ if (w==tmp){ num++; } } return num>nums.length/2?tmp:-1; } }

---

持续更新中…