- 📢前言
- 🌲原题样例：多数元素
- 🌻C#方法：投票法
- 🌻Java 方法一：哈希表
- 🌻Java 方法二：随机化
- 💬总结
- 🚀往期优质文章分享
📢前言
| 🚀 算法题 🚀 |
- 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
- 🌲 提示：本专栏解题 编程语言一律使用 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两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
🚀往期优质文章分享
- ❤️Unity零基础到入门 | 游戏引擎 Unity 从0到1的 系统学习 路线【全面总结-建议收藏】！
- 🧡花一天时间做一个高质量飞机大战游戏，过万字Unity完整教程！漂亮学妹看了直呼666！
- 💛回忆童年和小伙伴一起玩过的经典游戏【炸弹人小游戏】制作过程+解析
- 💚通宵一晚做出来的一款类似CS的第一人称射击游戏Demo！原来做游戏也不是很难
- 🤍爆肝整整一个周末写一款类似 皇室战争 的 即时战斗类 游戏Demo！两万多字游戏制作过程+解析！
- 💙一款类似“恐龙快打”的 横版街机格斗游戏 该如何制作？| 一起来学习 顺便送源码【码文不易，建议收藏学习】
- 💜【超实用技巧】| 提高写文的质量 和 速率必学技能： Typora 图床配置 详细说明