西海岸新区城市建设局公示网站,为什么做电影网站没有流量,苏州十大软件公司,wordpress怎么上传自己的网站题目
数组中有一个数字出现的次数超过数组长度的一半#xff0c;请找出这个数字。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 限制#xff1a;
1 数组长度 50000 解题思路
前置知…题目
数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。
你可以假设数组是非空的并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 限制
1 数组长度 50000 解题思路
前置知识 摩尔投票算法 摩尔投票算法是一种用于在数组中查找出现次数超过一半的元素的有效算法。算法的核心思想是利用候选元素和计数器进行投票通过消除不同元素之间的抵消来找到出现次数超过一半的元素。 算法原理 如果数组中存在一个出现次数超过一半的元素那么这个元素的剩余部分一定会抵消其他元素的出现次数最终剩下的就是该元素。 算法步骤 初始化候选元素 candidate 为数组的第一个元素计数器 count 为 1。 从数组的第二个元素开始遍历。 如果当前元素与候选元素相同则将计数器 count 加 1。 如果当前元素与候选元素不同则将计数器 count 减 1。 如果计数器 count 减为零则更新候选元素为当前元素并将计数器 count 重置为 1。 完成遍历后候选元素就是出现次数超过一半的元素。举个例子: 假设数组为 [2, 2, 1, 1, 1, 2, 2]。 初始时候选元素 candidate 为 2计数器 count 为 1。 开始遍历数组 遍历到 2与候选元素相同计数器 count 加 1计数器变为 2。 遍历到 1与候选元素不同计数器 count 减 1计数器变为 1。 遍历到 1与候选元素不同计数器 count 减 1计数器变为 0。 计数器 count 变为 0更新候选元素为当前元素 1计数器 count 重置为 1。 遍历到 1与候选元素相同计数器 count 加 1计数器变为 2。 遍历到 2与候选元素相同计数器 count 加 1计数器变为 1。 遍历到 2与候选元素相同计数器 count 加 1计数器变为 0。 计数器count变为0更新候选元素为当前元素2计数器count重置为2 完成遍历后候选元素为 2它是出现次数超过一半的元素 大概了解了摩尔算法后我们来看一下这道题 1.题目要求我们查找出出现的次数超过数组长度的一半的数字我们来画图看一下 2.首先我们先判断一下数组的长度若数组长度小于2那么我们直接返回数组中的第一个数字这个数字就为众数。 3.当数组长度大于2时我们就使用摩尔投票算法进行查找 举个例子[1, 2, 3, 2, 2, 2, 5, 4, 2] 我们设置一个变量 cur 去记录当前元素我们先将nums[0]放入再设置一个变量 sum用于记录当前元素 cur 的票数 4.然后我们开始遍历数组nums因为已经将nums[0] 放进了cur中所以我们从nums[1]开始遍历i 1 时nums[i] 2此时sum 不等于0所以 我们不用重新赋值我们去判断cur 是否等于 nums[1] ,此时cur ! nums[1] 所以我们要将 sum -- 5.再往后遍历时我们发现sum等于0所以我们只需要对cur重新赋值即可并将sum 变为1 6.按照摩尔投票的思路一直遍历到数组的最后一位保存再 cur 中的数就是我们要求的中位数。 代码实现
class Solution {public int majorityElement(int[] nums) {//首先我们判断一下数组中的元素是否小于2若小于2则直接返回if(nums.length 2){return nums[0];}//用于存放当前元素int cur nums[0];//用于存放出现次数int sum 1;//开始遍历数组for(int i 1; i nums.length; i){//如果出现次数为0就重新给当前元素赋值if(sum 0){cur nums[i];sum 1;}else{//如果所判断的元素等于当前存放的元素次数就加一if(cur nums[i]){sum;//如果所判断的元素不等于当前存放的元素次数就减一}else{sum--;}}}return cur;}
}
测试结果
