169 多数元素

题目

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

你可以假设数组是非空的,并且给定的数组总是存在众数。

示例 1:

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

示例 2:

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

实现

第一种:利用排序的方法

C# 语言

  • 状态:通过
  • 44 / 44 个通过测试用例
  • 执行用时:192 ms
public class Solution 
{
    public int MajorityElement(int[] nums) 
    {
        nums = nums.OrderBy(a => a).ToArray();
        return nums[nums.Length / 2];
    }
}

Python 语言

  • 执行结果:通过
  • 执行用时:48 ms, 在所有 Python3 提交中击败了 82.08% 的用户
  • 内存消耗:15.2 MB, 在所有 Python3 提交中击败了 6.90% 的用户
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

第二种:利用 Boyer-Moore 投票算法

寻找数组中超过一半的数字,这意味着数组中其他数字出现次数的总和都是比不上这个数字出现的次数。即如果把 该众数记为 +1 ,把其他数记为 −1 ,将它们全部加起来,和是大于 0 的。

  • 状态:通过
  • 44 / 44 个通过测试用例
  • 执行用时:148 ms
public class Solution 
{
    public int MajorityElement(int[] nums) 
    {
        int candidate = nums[0];
        int count = 1;
        for (int i = 1; i < nums.Length; i++)
        {
            if (count == 0)
                candidate = nums[i];

            count += (nums[i] == candidate) ? 1 : -1;
        }
        return candidate;      
    }
}