潍坊网站制作 熊掌号,医疗器械查询,软件设计思路,昆明网站seo外包229. 求众数 II
给定一个大小为 n 的整数数组#xff0c;找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1#xff1a;输入#xff1a;[3,2,3]
输出#xff1a;[3]示例 2#xff1a;输入#xff1a;nums [1]
输出#xff1a;[1]示例 3#xff1a;输入#xff1a;…229. 求众数 II
给定一个大小为 n 的整数数组找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1输入[3,2,3]
输出[3]示例 2输入nums [1]
输出[1]示例 3输入[1,1,1,3,3,2,2,2]
输出[1,2]解题思路
摩尔投票法的变种维护出现频次最大的两个元素如果新元素不和这两个元素任意一个相等则对这两个元素的出现频次进行抵消一旦频次为0最大的两个元素则被新加入的元素替换替换 假设只有一个元素出现超过 ⌊ n/3 ⌋ 次的元素所以元素分为了2批一批为出现超过 ⌊ n/3 ⌋ 次的元素n另一批为除此以外的少于2/3元素a在最极端的情况下我们n中的元素不断被抵消而a中的元素每次抵消也需要消耗两个元素因为n的出现次数是大于1/3的所以即使每次抵消3个元素以后n最后仍然会剩余元素。 假设只有一个元素出现超过 ⌊ n/3 ⌋ 次的元素所以元素分为了3批两批为出现超过 ⌊ n/3 ⌋ 次的元素n1n2另一批为除此以外的少于1/3元素a在最极端的情况下最大元素为n1和a因此新元素n2不断加入来抵消n1和a的频次但是因为n2的出现次数必定大于a所以a最先会被抵消完所以最大的元素就会被替换成为n1和n2
代码
func majorityElement(nums []int) []int {n1,n2,cnt1,cnt2:0,0,0,0for _,i : range nums {if cnt10i n1 {cnt1} else if cnt20i n2 {cnt2} else if cnt1 0 {n1 icnt1} else if cnt2 0 {n2 icnt2} else {cnt1--cnt2--}}v1,v2:0,0for _,i : range nums {if cnt10in1 {v1}if cnt20in2 {v2}}res : []int{}if cnt10v1len(nums)/3 {res append(res, n1)}if cnt20v2len(nums)/3 {res append(res, n2)}return res
}
