📢前言
🚀 算法题 🚀
🌲 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程😜
🌲 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
🌲 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧🧐!
🌲 今天是力扣算法题持续打卡第45天🎈!
🚀 算法题 🚀
🌲原题样例:多数元素
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3] 输出:3
示例 2:
输入:[2,2,1,1,1,2,2] 输出:2
提示:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案
🌻C#方法:投票法
众数总比非众数多 因此最终能让票数count保持大于0的数就是众数。
注意:每当count变回0时就更换候选人,继续统计后续票数。
思路解析
代码:
public class Solution { public int MajorityElement(int[] nums) { //投票法 int condidate = nums[0]; int count = 1; for(int j = 1;j<nums.Length;j++) { if(count == 0) { count = 1; condidate = nums[j]; continue; } if(nums[j] != condidate) { count--; } else { count++; } } return condidate; } }
执行结果
通过 执行用时:108 ms,在所有 C# 提交中击败了76.44%的用户 内存消耗:29.8 MB,在所有 C# 提交中击败了27.49%的用户
🌻Java 方法一:哈希表
思路解析
我们知道出现次数最多的元素大于⌊ 2/n⌋ 次,所以可以用哈希表来快速统计每个元素出现的次数。
我们使用哈希映射(HashMap)来存储每个元素以及出现的次数。对于哈希映射中的每个键值对,键表示一个元素,值表示该元素出现的次数。
我们用一个循环遍历数组nums并将数组中的每个元素加入哈希映射中。在
这之后,我们遍历哈希映射中的所有键值对,返回值最大的键。
我们同样也可以在遍历数组 nums时候使用打擂台的方法,维护最大的值,这样省去了最后对哈希映射的遍历。
代码:
class Solution { private Map<Integer, Integer> countNums(int[] nums) { Map<Integer, Integer> counts = new HashMap<Integer, Integer>(); for (int num : nums) { if (!counts.containsKey(num)) { counts.put(num, 1); } else { counts.put(num, counts.get(num) + 1); } } return counts; } public int majorityElement(int[] nums) { Map<Integer, Integer> counts = countNums(nums); Map.Entry<Integer, Integer> majorityEntry = null; for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) { majorityEntry = entry; } } return majorityEntry.getKey(); } }
执行结果
通过 执行用时:13 ms,在所有 Java 提交中击败了21.51%的用户 内存消耗:38.6 MB,在所有 Java 提交中击败了52.15%的用户
复杂度分析
时间复杂度:O( n ) 空间复杂度:O( n )
🌻Java 方法二:随机化
代码:
class Solution { private int randRange(Random rand, int min, int max) { return rand.nextInt(max - min) + min; } private int countOccurences(int[] nums, int num) { int count = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == num) { count++; } } return count; } public int majorityElement(int[] nums) { Random rand = new Random(); int majorityCount = nums.length / 2; while (true) { int candidate = nums[randRange(rand, 0, nums.length)]; if (countOccurences(nums, candidate) > majorityCount) { return candidate; } } } }
执行结果
通过 执行用时:1 ms,在所有 Java 提交中击败了99.96%的用户 内存消耗:44.5 MB,在所有 Java 提交中击败了12.18%的用户
💬总结
- 今天是力扣算法题打卡的第四十五天!
- 文章采用
C#
和Java
两种编程语言进行解题 - 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们