巨野县城乡和住房建设局网站,网站页面设计流程,临沂建设网站公司,腾讯广告代理题目描述
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1#xff1a;
输入#xff1a; nums [3,2,3] 输出#xf…题目描述
给定一个大小为 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
代码及注释
func majorityElement(nums []int) int {res : 0count : 0for _, num : range nums {if num res {count // 如果当前数字与候选数字相同则计数加1} else if count 0 {res num // 如果当前数字与候选数字不同且计数为0则更新候选数字} else {count-- // 如果当前数字与候选数字不同且计数不为0则计数减1}}return res
}代码解释
使用的是摩尔投票算法来找出数组中的主要元素。摩尔投票算法是一种高效的算法可以在O(n)的时间复杂度内找出数组中出现次数超过一半的元素如果存在的话。
这里的逻辑是
使用变量res初始化为0这里假设数组中没有0和计数count初始化为0。遍历数组nums对于数组中的每一个数字 如果当前数字与候选数字res相同则计数count加1。如果当前数字与候选数字res不同且计数count为0则更新候选数字res为当前数字。如果当前数字与候选数字res不同且计数count不为0则计数count减1。 最后res就是数组中的主要元素。
这个方法的时间复杂度是O(n)其中n是数组nums的长度。
