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

2023-12-22 20:11:08

?目录

题目描述

实现

提交结果


题目描述

给定一个大小为 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
}

提交结果

6aba55829045423eae081d3f46f147e9.png

解答可能并不唯一,仅供参考哦!

文章来源:https://blog.csdn.net/HYZX_9987/article/details/135152934
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。