每日一练Day05：寻找多数元素

落日映苍穹つ 2024-04-01 17:01 107阅读 0赞

#### 目录 ####

*  多数元素I
 *   *  1、方法一
     *  2、方法二

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

这道题来自LeetCode，下面我们来抽丝剥茧，细品一下解题思想。

## 多数元素I ##

![c6b14d80ad37473c8180c9f1896f2aba.png][]  
**题目特点：**大小为`n`非空数组，并且给定的数组**总是存在**多数元素、返回其中出现次数大于`n/2`的元素——多数元素

### 1、方法一 ###

**思路1：**  
由于给定数组大小为n，所以出现次数大于n/2的元素至多只有一个，如果我们将给定数组排序，那么数组中出现次数超过一半\[n/2\]的数字，一定是排好序之后，中间位置的数字。

**理论成立，实践开始：**

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

测试结果：

![a3e2d40a8dae4f338e6eff3dad85f038.png][]

### 2、方法二 ###

**思路2：**摩尔投票法  
首先我们先了解一下摩尔投票法，摩尔投票法主要分为两个阶段即**抵消阶段**和**计数阶段**：

> **抵消阶段：** 如果两个不同候选人的投票进行对抗，则抵消掉一张票，如果两个投票相同，则累加抵消次数。如果计票为0，则换候选人，继续重复上述步骤。  
>   
> **计数阶段：** 在抵消阶段最后得到的抵消计数只要不为0，那个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数才可确定。

例如找出数组`array=[2,3,1,3,3,2,3]`中的大于n/2的多数元素，可分解为下述过程：

![90faca3caabe4527a29dba35b4f2daa5.png][]

**理论成立，实践开始：**

**注：** 对于这道题，由于题目已经明确说明给定的数组总是存在多数元素，所以可以省去验证步骤。

public int majorityElement(int[] nums) {
        
            //初始化候选人和他们的计票
            int count=0;
            int tmp=nums[0];
            for (int i = 0; i < nums.length; i++) {
        
                //增加抵消次数
                if(nums[i]==tmp) {
        
                    count++;
                } else {
        
                    //抵消一票
                    count--;
                }
                //计票数为0，换候选人
                if(count==0) {
        
                    tmp=nums[i+1];
                }
            }
            return tmp;
        }

测试结果：

![a3e2d40a8dae4f338e6eff3dad85f038.png][]

\------------------ （本章完）------------------

[c6b14d80ad37473c8180c9f1896f2aba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0c8e8f884d164d9d887bbb70ed95efff.png
[a3e2d40a8dae4f338e6eff3dad85f038.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/80bf4823da6247c68b12771d1734c1df.png
[90faca3caabe4527a29dba35b4f2daa5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e19a99ffb482440489a52a99dc5bf8ff.png