Leetcode-面试题 17.10. 主要元素(摩尔投票法)

电玩女神 2023-02-22 08:06 11阅读 0赞

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

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

> 面试题 17.10. 主要元素  
> 题目链接：[https://leetcode-cn.com/problems/find-majority-element-lcci/][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][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;
    
           }
    }

--------------------

**持续更新中…**

[https_leetcode-cn.com_problems_find-majority-element-lcci]: https://leetcode-cn.com/problems/find-majority-element-lcci/
[https_www.zhihu.com_question_49973163]: https://www.zhihu.com/question/49973163