class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
}
};
229. 多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3] 输出：[3]
示例 2：
输入：nums = [1] 输出：[1]
示例 3：
输入：nums = [1,2] 输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 14.2 MB, 提交时间: 2020-11-20 15:18:22
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
# 摩尔投票法, 最多选中两个
n = len(nums)
if n < 2:
return nums
cand_1, cand_2 = nums[0], nums[0] # 两个候选人
count_1, count_2 = 0, 0 # 两个候选人可抵消票数(多出的)
# 配对阶段
for num in nums:
if num == cand_1:
count_1 += 1
continue
elif num == cand_2:
count_2 += 1
continue
if count_1 == 0: # 候选人1的可抵消票数空了, 换候选人
cand_1 = num
count_1 += 1
continue
elif count_2 == 0:
cand_2 = num
count_2 += 1
continue
# 未发生换候选人以及已有候选人增加可抵消票数的情况, 两个候选人都减票(抵消但仍为候选人)
count_1 -= 1
count_2 -= 1
# 计票阶段
count_1 = nums.count(cand_1)
count_2 = nums.count(cand_2)
# 公布结果(注意去重)
ans = []
if count_1 * 3 > n:
ans.append(cand_1)
if count_2 * 3 > n and cand_2 != cand_1:
ans.append(cand_2)
return ans
golang 解法, 执行用时: 16 ms, 内存消耗: 4.9 MB, 提交时间: 2020-11-20 14:44:09
func majorityElement(nums []int) []int {
dic := make(map[int]int, 1)
ans := []int{}
n := len(nums)
threhold := n/3
var addmap = make(map[int]bool, 1)
for _, num := range nums {
dic[num]++
if dic[num] > threhold && addmap[num] == false {
ans = append(ans, num)
addmap[num] =true
}
}
return ans
}
golang 解法, 执行用时: 20 ms, 内存消耗: 5 MB, 提交时间: 2020-11-20 14:41:41
func majorityElement(nums []int) []int {
dic := make(map[int]int, 1)
ans := []int{}
n := len(nums)
for _, num := range nums {
dic[num]++
}
for k, v := range dic {
if v > n/3 {
ans = append(ans, k)
}
}
return ans
}
python3 解法, 执行用时: 44 ms, 内存消耗: 14.2 MB, 提交时间: 2020-11-20 14:29:52
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
ans, n = [], len(nums)
map_ = collections.Counter(nums)
for c, q in map_.items():
if q * 3 > n:
ans.append(c)
return ans