刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/majority-element/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路

一定存在多数元素的话，那么多数元素的计数值一定大于其他元素计数值的和，所以两数相减一定是大于零的

顺便存取当前计数大于零的元素，留下来的就是结果了

代码也基本就出来了。老样子，细节在代码注释

代码

// 这里不用结构也可，直接两个变量就OK
type count struct {
	Key   int
	Count int
}

func majorityElement(nums []int) int {
	counts := make([]*count, 0, 1)
	for _, num := range nums {
		if len(counts) == 0 {
			counts = append(counts, &count{
				Key:   num,
				Count: 1,
			})
			continue
		}
        // 多数元素最终一定会在key里，且计数大于0
        // 不同的数据就减一，相同元素就+1，那么最后留下的一定是多数元素
		if counts[0].Key == num {
			counts[0].Count++
		} else if counts[0].Key != num && counts[0].Count == 0 {
			counts[0].Key = num
			counts[0].Count = 1
		} else {
			counts[0].Count--
		}
	}
	return counts[0].Key
}