算法学习第十二天

1.第12天 多数元素今日任务169. 多数元素 尝试多种解法提交第二周学习小结题意给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。题目链接https://leetcode.cn/problems/majority-element/官方题解https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/2.给定一个非空数组多数元素定义在数组中出现次数 大于 ⌊n/2⌋ 的元素。题目保证一定存在这个多数元素不用考虑特殊情况。简单理解数组里有一个数出现次数超过一半我们要把它找出来。示例nums [3,2,3] 多数元素3nums [2,2,1,1,1,2,2]多数元素2思路用哈希表key存数组元素value存出现次数遍历数组逐个统计每个数字出现多少次遍历哈希表找到出现次数大于n/2的元素直接返回。3.这周从链表过渡到数组刷题知识点衔接很顺畅。一开始只会暴力双层循环现在慢慢学会用双指针、哈希表、特殊算法优化代码。#include vectorusing namespace std;class Solution {public:int majorityElement(vectorint nums) {int res 0;int count 0;for(int num : nums){if(count 0){// 更换候选元素res num;}if(num res){count;}else{count--;}}return res;}};