云虚拟主机可以做视频网站不,做公司网站大概多少钱,山西建设厅报名网站,网站建设的主要职责2024/5/21 起床走到阳台#xff0c;外面绵柔细雨#xff0c;手探出去#xff0c;似乎感受不到。刚到实验室#xff0c;窗外声音放大#xff0c;雨大了。昨天的两题任务中断了#xff0c;由于下雨加晚上有课。这样似乎也好#xff0c;不让我有一种被强迫的感觉#xff0…2024/5/21 起床走到阳台外面绵柔细雨手探出去似乎感受不到。刚到实验室窗外声音放大雨大了。昨天的两题任务中断了由于下雨加晚上有课。这样似乎也好不让我有一种被强迫的感觉随心所欲些也好做题
1、题目描述 2、逻辑分析
题目要求就是找出在数组中数量占比大于整个数组长度n的一半的元素。我的思路第一步将数组里面的元素遍历记录出现的个数第二步将他们与n/2比较。
在这里我突然又想到数量超过一般的元素具有唯一性那么算法可不可以优化一下将数组中存在数量最多的元素来跟n/2比较。这里使用哈希表。
3、代码演示
public int majorityElement(int[] nums) {// 使用一个Map来统计每个数字出现的次数 MapInteger, Integer counts countNums(nums);// 定义一个变量来存储多数元素及其计数初始化为nullMap.EntryInteger, Integer majorEntry null;// 遍历Map中的每个元素for(Map.EntryInteger, Integer entry : counts.entrySet()){// 如果majorEntry是null或者当前元素的计数大于majorEntry的计数if(majorEntry null || entry.getValue() majorEntry.getValue()){// 更新majorEntry为当前元素 majorEntry entry;}}// 返回多数元素的键即多数元素本身return majorEntry.getKey();}// 定义一个私有方法用于统计数组中每个数字的出现次数并返回结果Map private MapInteger,Integer countNums (int [] nums){// 创建一个HashMap来存储数字及其出现次数MapInteger , Integer counts new HashMapInteger, Integer();for(int num : nums){// 如果该数字尚未在Map中出现过if(!counts.containsKey(num)){// 将该数字添加到Map中并设置其出现次数为1counts.put(num,1);}else{// 如果该数字已在Map中出现过则增加其出现次数counts.put(num,counts.get(num) 1);}}// 返回存储了每个数字及其出现次数的Mapreturn counts;}这里使用了哈希表将元素作为键元素的数量作为值。然后遍历哈希表找到键值对中值最大的元素最后返回该元素。技术难点是对哈希表还是不够熟练特别是map.entry这里都不知道还可以这样用。
时间复杂度O(n)空间复杂度O(n)。
这道题的解法好多啊还有排序、随机化、分治、Boyer-Moore 投票算法。
下面我们主要来说一下最后一个Boyer-Moore 投票算法也称为摩尔投票算法。官方的思路解法太过于官方这里选取了其他题解 下面直接看代码
public int majorityElement(int[] nums) {// 计数器用于追踪当前候选的多数元素的数量int count 0;// 候选的多数元素 Integer candidate null;// 遍历数组中的每个元素for(int num : nums){// 如果计数器为0则更新候选的多数元素为当前遍历到的元素if(count 0){candidate num;}// 如果当前元素与候选的多数元素相同则计数器加1否则减1 count (num candidate) ? 1 : -1;}// 返回候选的多数元素return candidate;}时间复杂度O(n)空间复杂度O(1)。
