[剑指offer][JAVA]面试题第[39]题[数组中出现次数超过一半的数字][HashMap][摩尔投票法]

矫情吗；* 2023-02-20 13:32 96阅读 0赞

#### 【问题描述】\[简单\] ####

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
    
    你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    
    
    示例 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];
            HashMap<Integer, Integer> map=new HashMap<Integer, 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;
        }

HashMap<Integer, 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. 摩尔投票法 最佳 ######

**核心理念为 “正负抵消”**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 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;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

###### 3. 数组排序法 ######

将数组 nums 排序，由于众数的数量超过数组长度一半，因此 数组中点的元素 一定为众数。  
**时间复杂度：O(NlogN) 空间复杂度：O(1)**

public int majorityElement(int[] nums) { 
            Arrays.sort(nums);
            return nums[nums.length/2];
        }

#### 【总结】 ####

###### 1.Java中HashMap遍历几种方式 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]

###### 2.HashMap常用语法 ######

1.import java.util.HashMap;//导入;

2.HashMap<K, V> map=new HashMap<K, V>();//定义map，K和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();//浅克隆，类型需要强转；如HashMap<String , Integer> map2=(HashMap<String, 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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627115327119.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200627115345257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200627115357543.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200627115420926.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200627115822748.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200627115830953.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70