LeetCode题目之腾讯精选练习（50题）：求众数

系统管理员 2024-04-18 15:04 95阅读 0赞

# 题目 #

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

你可以假设数组是非空的，并且给定的数组总是存在众数。  
**示例 1** :

输入: [3,2,3]
    输出: 3

**示例 2** :

输入: [2,2,1,1,1,2,2]
    输出: 2

## 实现代码 ##

public int MajorityElement(int[] nums)
    {
        
        Array.Sort(nums);//排序
        int i = 0;//记录元素的位置
        int n = 0;//记录元素的出现次数
        while (n <= nums.Length / 2)
        {
        
            n = 1;
            for (; i < nums.Length && nums[i] == nums[i + 1]; i++)
            {
        
                n++;
            }
            i++;
        }
        return nums[i - 1];
    }

## 执行结果 ##

**执行结果**：通过  
**执行用时** : 172 ms, 在所有 C\# 提交中击败了81.46%的用户  
**内存消耗** : 28.6 MB, 在所有 C\# 提交中击败了5.06%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

首先想到的是排序，然后进行统计。后来看官方题解，觉得Boyer-Moore 投票算法很厉害，先按照这种想法自己设计了算法，还是比官方复杂。

## Boyer-Moore 投票算法 ##

自己的算法

public int MajorityElement(int[] nums)
    {
        
        int i = 1; //记录元素位置
        int sum = 1;//计数器
        int houxuan = nums[0];//候选数字
        while (i < nums.Length)
        {
        
            if (nums[i] != houxuan)
                sum--;
            else
                sum++;
            if (sum == 0)
            {
        
                houxuan = nums[++i];
                sum = 1;
            }
            i++;
        }
        return houxuan;
    }

![在这里插入图片描述][20190908171604430.png]  
官方题解

public int MajorityElement(int[] nums)
    {
        
        int count = 0;
        int candidate = 0;
    
        foreach (var num in nums)
        {
        
            if (count == 0)
            {
        
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
    
        return candidate;
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9553e9c4bada48ddb7453d3af73a3893.png
[20190908171604430.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4a93c475458a4fe08fc11d50ea9b29ab.png
[20190908171636604.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5b42b11fc6cf4dffadc5fd801c1ae380.png