微网站建设报价方案模板下载,seo顾问,松原建设网站,做艺术网站素材题目链接#xff1a;https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
1. 题目介绍#xff08;39. 数组中出现次数超过一半的数字#xff09; 数组中有一个数字出现的次数超过数组长度的一半#xff0c;请找出这个数字。 你可…题目链接https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
1. 题目介绍39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。 你可以假设数组是非空的并且给定的数组总是存在多数元素。 【测试用例】 示例1 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 【条件约束】 提示 1 数组长度 50000 【相关题目】 注意本题与主站 169. 多数元素 题目相同。 2. 题解
2.1 暴力穷举 – O(n2)
时间复杂度O(n2)空间复杂度O(n) 【解题思路】 对于排序数组我们可以很容易统计出每个数字出现的次数可参考 剑指 Offer 53 - I. 在排序数组中查找数字 I 然后再对次数进行判断看是哪个数字出现的次数超过了数组长度的一半。 …… 【实现策略】 对输入数组 nums 使用 sort() 方法进行升序排序 【sort()方法详解】详述Java中sort排序函数定义一个 HashMap 用来记录每个数字在数组中出现的次数数组中数组为键出现的次数为值 【注意点】HashMap 的键虽然不能重复但是如果是有重复键的键值对要加入那么 新值会覆盖掉旧值切记双循环穷举当然下面为了提高效率同时防止重复键值对被覆盖通过每次循环中把 j 赋值给 i 的操作这样就保证了内循环结束后i 位于当前重复数字的末尾而由于循环结束i 的原因这样就相当于间接的移动 i 到了下一个非重复数组数字的位置然后进行下一个数字重复次数的统计这里的双循环穷举可以改为 一次遍历 二分查找找左右边界 的方式进一步提高统计效率最后遍历 HashMap找出次数超过数组一半的数字并返回。 class Solution {public int majorityElement(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 遍历数组// 定义map用来记录每个数字在数组中出现的次数HashMapInteger,Integer map new HashMap();int n 0;for(int i 0; i nums.length; i){for (int j i; j nums.length; j){if (nums[j] nums[i]) {n;i j; // 将i移到下一个数的位置} }map.put(nums[i],n);n 0;}// 遍历map找出超过一半数组长度的数字for(Map.EntryInteger,Integer entry : map.entrySet()){if (entry.getValue() nums.length/2) return entry.getKey();}return 0;}
}代码简化 【实现策略】 看了题解意识到自己傻冒了忘了 HashMap 中有 containsKey() 方法了那么完全可以直接一次遍历数组 nums 用 HashMap 统计各数字的数量即可找出 众数 根本不用双循环一个一个对比直接单次循环 containsKey(下一个数字) 有就没有就移动到下一个就完了此方法时间和空间复杂度均为 O(n) 。 一次遍历在遍历的过程中将数组数字存入 HashMap 判断 HashMap 的键是否已有当前数字有就加1没有就下一个。 …… 但是不知道为啥这样好慢比没简化的代码要慢的多估计应该是力扣的测试用例设置的不太好。 class Solution {public int majorityElement(int[] nums) {// 遍历数组// 定义map用来记录每个数字在数组中出现的次数HashMapInteger,Integer map new HashMap();for(int i 0; i nums.length; i){if (!map.containsKey(nums[i])) map.put(nums[i],1);else map.put(nums[i], map.get(nums[i])1);}// 遍历map找出超过一半数组长度的数字for(Map.EntryInteger,Integer entry : map.entrySet()){if (entry.getValue() nums.length/2) return entry.getKey();}return 0;}
}2.2 数组排序法 – O(nlogn)
时间复杂度O(nlogn)空间复杂度O(1) 【解题思路】 将数组 nums 排序数组中点的元素 一定为众数。 根据题目所出的数组特性数组中有一个数字出现的次数超过了数组长度的一半那么如果对这个数组进行排序排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。 …… 【实现策略】 根据上面的思路代码就变的异常的轻松加愉快 排序返回数组的中点数字 …… 当然如果返回值一变要求返回该数字的重复次数这个方法就趴菜了不过题目摇身一变就变成了剑指 Offer 53 - I. 在排序数组中查找数字 I 可用 2.1 中的方法解决。 class Solution {public int majorityElement(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 遍历数组return nums[nums.length/2];}
}2.3 摩尔投票法原书题解2 – O(n)
时间复杂度O(n)空间复杂度O(1) 【解题思路】 核心理念为 票数正负抵消因为题目中明确的指出了要返回的数字是在数组中出现次数超过一半的数字那么通过正负抵消最后能留下的一定是该数字。 推论一 若记 众数 的票数为 1非众数 的票数为 -1则一定有所有数字的 票数和 0 推论二 若数组的前 a 个数字的 票数和 0 则 数组剩余 (n−a) 个数字的 票数和一定仍 0 即后 (n−a) 个数字的 众数仍为 x 。 …… 【实现策略】 定义 x 存储众数候选人定义票数 votes一次遍历判断当前票是否是给当前候选人的如果是则加1如果不是则减1当候选人的票数为0时则更换新的候选人。 …… 【唠叨两句】 原书题解1 采用了快排思想的排序方法 Partition() 一直到 Partition() 方法随机到中点即将比中点数小的数字移到数组的左边比中点数大的数组移到数组的右边。此方法可以但没必要除非题目要求不能使用库函数不然感觉倒是没必要自己写排序 class Solution {public int majorityElement(int[] nums) {int x 0, votes 0, count 0;for(int num : nums){if(votes 0) x num;votes num x ? 1 : -1;}// 验证 x 是否为众数for(int num : nums)if(num x) count;return count nums.length / 2 ? x : 0; // 当无众数时返回 0}
} 3. 参考资料
[1] 剑指 Offer 39. 数组中出现次数超过一半的数字摩尔投票法清晰图解 [2] Java遍历Map的几种方法 [3] 【Java】 剑指offer(53-1) 数字在排序数组中出现的次数
