169. 多数元素

素颜马尾好姑娘i 2023-07-13 15:26 27阅读 0赞

# 题目： #

[169. 多数元素][169.]  
[面试题39. 数组中出现次数超过一半的数字][39.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

## 1. 最原始的思路： ##

先排序，然后遍历整个数组，对记录每个数值出现的次数进行统计即可。

## 2. 排序法： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]

## 3. 摩尔投票法：（首选） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 8]

# 代码： #

## 1. 最原始的思路： ##

/** * code169 */
    import java.util.*;
    
    public class code169 { 
    
        public static int majorityElement(int[] nums) { 
            if (nums.length == 1) { 
                return nums[0];
            }
            Arrays.sort(nums);
            int count = 1;
            int res = -1;
            for (int i = 0; i < nums.length - 1; i++) { 
                if (nums[i] == nums[i + 1]) { 
                    count++;
                } else { 
                    count = 1;
                }
                if (count > (nums.length - 1) / 2) { 
                    res = nums[i];
                }
            }
            return res;
        }
    
        public static void main(String[] args) { 
            int nums1[] = {  3, 2, 3 };
            int nums2[] = {  2, 2, 1, 1, 1, 2, 2 };
            int ans1 = majorityElement(nums1);
            int ans2 = majorityElement(nums2);
            System.out.println(ans1 + " " + ans2);
        }
    }

## 2. 排序法： ##

/** * code169 */
    import java.util.*;
    
    public class code169 { 
    
        public static int majorityElement(int[] nums) { 
            Arrays.sort(nums);
            return nums[nums.length / 2];
        }
    
        public static void main(String[] args) { 
            int nums1[] = {  3, 2, 3 };
            int nums2[] = {  2, 2, 1, 1, 1, 2, 2 };
            int ans1 = majorityElement(nums1);
            int ans2 = majorityElement(nums2);
            System.out.println(ans1 + " " + ans2);
        }
    }

## 3. 摩尔投票法：（首选） ##

/** * code169 */
    import java.util.*;
    
    public class code169 { 
    
        // 摩尔投票法：
        public static int majorityElement(int[] nums) { 
            int candidate = nums[0];
            int count = 1;
            for (int i = 1; i < nums.length; i++) { 
                if (candidate == nums[i]) { 
                    count++;
                } else { 
                    count--;
                }
                if (count == 0) { 
                    candidate = nums[i];
                    count = 1;
                }
            }
            return candidate;
        }
    
        public static void main(String[] args) { 
            int nums1[] = {  3, 2, 3 };
            int nums2[] = {  2, 2, 1, 1, 1, 2, 2 };
            int ans1 = majorityElement(nums1);
            int ans2 = majorityElement(nums2);
            System.out.println(ans1 + " " + ans2);
        }
    }

# 参考： #

1.  [多数元素][Link 1]
2.  [Java-3种方法(计数法/排序法/摩尔投票法)][Java-3]
3.  [独乐乐不如众乐乐，如何装逼的求众数！][Link 2]
4.  [面试题39. 数组中出现次数超过一半的数字（摩尔投票法，清晰图解）][39. 1]
5.  [java中向上向下及四舍五入取整的方法，double型强制转换成int型的取整方法？][java_double_int]
6.  [如何理解摩尔投票算法？][Link 3]

[169.]: https://leetcode-cn.com/problems/majority-element/
[39.]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230529/9ce0c66c06444d4aafec467f042db64a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20230529/4b6f1b5db27d42bfbe81fc04414010e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: /images/20230529/0227a536ef9b41b390a8a39de6275a07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: /images/20230529/fa0d5df3308944238de34461f316d8f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: /images/20230529/fb269f8923024b088aa1d8cdd7c290d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]: /images/20230529/72d752df84354f3189a91bb3f87a567a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]: /images/20230529/0d4b22159d1846c7ae152d2d2f7ddb37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]: /images/20230529/d20071adb8804d60b767a60dd8345131.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 8]: /images/20230529/d5a87a5ffddf45988a0c5b7a9e34360d.png
[Link 1]: https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
[Java-3]: https://leetcode-cn.com/problems/majority-element/solution/3chong-fang-fa-by-gfu-2/
[Link 2]: https://leetcode-cn.com/problems/majority-element/solution/du-le-le-bu-ru-zhong-le-le-ru-he-zhuang-bi-de-qiu-/
[39. 1]: 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/
[java_double_int]: https://blog.csdn.net/xmc281141947/article/details/53887126
[Link 3]: https://www.zhihu.com/question/49973163