算法题系列7·获得数组中多数元素

?目录

题目描述

实现

提交结果

题目描述

给定一个大小为 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 * 10^4

-10^9 <= nums[i] <= 10^9

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

来源链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

实现

func majorityElement(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}

	num, count := nums[0], 1 // 原始base值，仅自己，默认已出现一次
	for j := 1; j < n; j++ {
		if num == nums[j] {
			count++
		} else { // 新出现的事物出现了一次，但不显式+1
			count-- // 此消彼长，在已出现的这些事物中当前持平
		}

		if count < 0 {
			num = nums[j]
			count = 1 // 给nums[j]重置为1
		}
	}

	return num
}

提交结果

解答可能并不唯一，仅供参考哦！