题目英文
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
题目中文
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
算法实现
第一种：利用排序的方式
public class Solution {public int MajorityElement(int[] nums) {nums = nums.OrderBy(a => a).ToArray();return nums[nums.Length / 2];}
}
第二种：利用 Boyer-Moore 投票算法
public class Solution {public int MajorityElement(int[] nums) {//寻找数组中超过一半的数字，这意味着数组中其他数字出现次数的总和都是比不上这个数字出现的次数。//即如果把 该众数记为 +1 ，把其他数记为 −1 ，将它们全部加起来，和是大于 0 的。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; }
}
实验结果
第一种方式：
- 状态：通过
- 44 / 44 个通过测试用例
- 执行用时：192 ms
第二种方式：
- 状态：通过
- 44 / 44 个通过测试用例
- 执行用时：148 ms
相关图文：
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：搜索二维矩阵
- LeetCode实战：将有序数组转换为二叉搜索树
- 资料分享：数学建模资料分享 – 图论部分
- 资料分享：数学建模资料分享 – 神经网络部分
- 如何利用 C# 实现 K 最邻近算法？
- 如何利用 C# 实现 K-D Tree 结构？
- 如何利用 C# + KDTree 实现 K 最邻近算法？
- 如何利用 C# 对神经网络模型进行抽象？
- 如何利用 C# 实现神经网络的感知器模型？
- 如何利用 C# 实现 Delta 学习规则？
- 如何利用 C# 实现 误差反向传播 学习规则？
- 如何利用 C# 爬取带 Token 验证的网站数据？
- 如何利用 C# 向 Access 数据库插入大量数据？
- 如何利用 C# + Python 破解猫眼电影的反爬虫机制？
