给定一个大小为
n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
思路：
常规的 hash表（空间复杂度为O(n)），以及排序算法（时间复杂度为O(nlogn)），都不满足题目的进阶要求，这里不做展开，具体可以参考LeetCode官方题解。
这里学到一种新的算法：参考 LeetCode视频题解（摩尔投票法），并以视频题解为基础，想到一种更容易理解的逻辑顺序，即：
- 若新来士兵与原有士兵【同一阵营】
- 若新来士兵与原有士兵【非同一阵营】
- 判断cnt是否为0...（详细见注释）
时间复杂度：O(n)
空间复杂度：O(1)
funcmajorityElement(nums []int) int { // 当前多数元素为winner，其个数为cntwinner, cnt :=nums[0], 1fori :=1; i<len(nums); i++ { // 若新来士兵与原有士兵【同一阵营】ifnums[i] ==winner { cnt++// 若新来士兵与原有士兵【非同一阵营】 } elseifnums[i] !=winner { // 新来士兵，发现当前阵营已经没有兵力，新士兵就成了领主，且其兵力+1ifcnt==0 { winner=nums[i] cnt++// 如果cnt减到0，就会立即重置新的winner，所以不可能出现cnt减到负数的情况 } else/* if cnt > 0 */ { cnt-- } } } returnwinner} // 视频题解给出的示例代码（逻辑和上面的其实大同小异，我仅仅改了下判断顺序的逻辑而已）：funcmajorityElement(nums []int) int { // 当前多数元素为winner，其个数为cntwinner, cnt :=nums[0], 1fori :=1; i<len(nums); i++ { ifnums[i] ==winner { cnt++ } elseifcnt==0 { winner=nums[i] cnt++ } else { cnt-- } } returnwinner}
