【LeetCode】169.多数元素（三种解法）

亦凉 2023-09-29 10:02 2阅读 0赞

## 问题描述 ##

这是LeetCode上的一道算法题，博主整理了三种解题思路和方法，希望可以帮助大家提升算法的思维。

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：\[3,2,3\]  
输出：3

示例 2：

输入：\[2,2,1,1,1,2,2\]  
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

来源：力扣（LeetCode）  
链接：[169.多数元素][169.]

## 一、解法1（双引用暴力求解）： ##

这是一个时间复杂度为O（n\*n）的算法，也是大多数人能想出来的算法。  
**每次从数组中取出一个元素，扫描一遍数组，查看这个元素出现的次数，当前元素出现次数 >= n / 2,即为答案。**  
代码如下：

public static void main(String[] args) {
        
            int[] arr = new int[]{
        2,2,1,1,1,2,2};
            int sum = find(arr);
            System.out.println(sum);
        }
    
        private static int find(int[] arr) {
        
    
            for (int i = 0; i < arr.length; i++) {
        
                int count=0;//设置计数器来统计每个元素出现的次数
                for (int j = 0; j < arr.length; j++) {
        
                    if (arr[i]==arr[j]){
        
                        count++;
                    }
                }
                if (count>arr.length/2){
        
                //当前元素出现次数 >n / 2,即为答案
                    return arr[i];
                }
            }
            return -1;
        }

## 二、解法2（排序后直接返回中间值）： ##

举个例子：  
![在这里插入图片描述][40e3bd80a0d64fe78603be3bc16193fc.png]  
**当把这些数字排好序后，出现次数 >n / 2的元素一定是数组中间的元素。**  
代码如下：

public static void main(String[] args) {
        
            int[] arr = new int[]{
        2,2,1,1,1,2,2};
            Arrays.sort(arr);
            System.out.println(arr[arr.length >> 1]);
        }

由于排序算法的时间复杂度最优最快也是O（nlogn），所以这个解法还不够完美。

## 三、解法3（摩尔投票法） ##

下面介绍一个巨牛的时间复杂度只有O（n）的算法。（**这个算法适用于任何众数问题**）。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAS2lsbGluZyBWaWJl_size_20_color_FFFFFF_t_70_g_se_x_16]

这个问题的本质就是候选人正票数和负票数的**抵消问题**，由于多数元素的得票数一定是>n/2，抵消后，票数一定是一个正数，最终胜出。

public static void main(String[] args) {
        
            int[] arr = new int[]{
        2,2,1,1,1,2,2};
            System.out.println(majorityElement(arr));
        }
    
    
        public static int majorityElement(int[] arr) {
        
            // 默认候选人就是第一个元素
            int candidate = arr[0];
            int count = 1;
            for (int i = 1; i < arr.length; i++) {
        
                if (arr[i] == candidate) {
        
                    count++;
                } else {
        
                    count--;
                    if (count == 0) {
        
                        // 更换候选人
                        candidate = arr[i];
                        count = 1;
                    }
                }
            }
            return candidate;
        }

**默认候选人就是第一个元素，然后给自己投一票（count=1），如果遇到相同的票则+1，否则-1。当count为0的时候换下一个人，并且重置票数为1（count=1）。**

## 四、 总结（摩尔投票法的推广） ##

**摩尔投票法的应用----众数问题**  
1.在一堆元素中，如果至多选择一个最多的元素，则他的票数>n/2.  
2.在一堆元素中，如果之多选择两个最多的元素，则他的票数>n/3.  
3.在一堆元素中，如果之多选择m个最多的元素，则他的票数>n/(m+1).

![在这里插入图片描述][2cf5e0e564ff450b9257478b231dc860.png]

> 1.因为出现次数大于n/3的元素最多只有两个，所以最开始可以维护两个数字(num1,num2)和两个计数器(counter1,counter2)；  
> 2.遍历数组，当数组中元素和num1或者num2相同，对应的counter1或者counter2加1；  
> 3.如果counter1或counter2为0，将遍历到的该元素赋给num1或者nums2；  
> 4.否则counter1和counter2都减1。

[169.]: https://leetcode-cn.com/problems/majority-element/
[40e3bd80a0d64fe78603be3bc16193fc.png]: https://img-blog.csdnimg.cn/40e3bd80a0d64fe78603be3bc16193fc.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAS2lsbGluZyBWaWJl_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3df3c961012c483b8e453d845d071890.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS2lsbGluZyBWaWJl,size_20,color_FFFFFF,t_70,g_se,x_16
[2cf5e0e564ff450b9257478b231dc860.png]: https://img-blog.csdnimg.cn/2cf5e0e564ff450b9257478b231dc860.png