文章目录
☀️ 前言 ☀️
算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！
🙀 作者简介 🙀
大家好，我是布小禅，一个尽力让无情的代码变得生动有趣的IT小白，很高兴能偶认识你，关注我，每天坚持学点东西，我们以后就是大佬啦！
📢 ：❤布小禅❤
📢 作者专栏：
这是我刷第 33/100 道力扣简单题
💗 一、题目描述 💗
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素
示例1：
输入：[3,2,3] 输出：3
示例2：
输入：[2,2,1,1,1,2,2] 输出：2
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题
💁 二、题目解析 💁
思路1：
哈希表法：
先创建一个哈希表、
如果长度为1，返回元素
遍历数组
如果元素在还行表的key里面，就让对应的值+1,
判断与n/2的大小，如果大，返回该元素
如果不在，初始化计数为1
如果遍历完，返回null
思 路 2
双指针法：
先将数组排序
然后创建一个变量记录同一元素出现的次数
遍历数组
判断计数
判断计数的大小
遍历结束，返回null
🏃 三、代码 🏃
☁️ 1️⃣. python ☁️
思路1
class Solution: def majorityElement(self, nums: List[int]) -> int: dir = {} # 创建哈希表 n = len(nums) # 变量n接收数组长度 if n==1: return nums[0] # 特殊情况 for i in range(n): # 遍历 if nums[i] in dir.keys(): # 如果元素在哈希表的key里面 dir[nums[i]]+=1 # 让对应的值+1 if dir[nums[i]]>n//2: return nums[i] # 判断与n/2的大小，如果大，返回该元素 else: dir[nums[i]] = 1 # 如果不在，初始化计数为1 return None # 如果遍历完，返回null
思路2
class Solution: def majorityElement(self, nums: List[int]) -> int: n = len(nums) # 数组长度 if n == 1: return nums[0] # 特殊情况 nums.sort() # 数组排序 m = 1 # 创建一个变量记录同一元素出现的次数 for i in range(n - 1): # 遍历数组 if nums[i] != nums[i + 1]: # 判断是否同一元素 if m > n / 2: return nums[i + 1] # 判断计数的大小 m = 1 elif nums[i] == nums[i + 1]: # 判断是否同一元素 m += 1 if m > n / 2: return nums[i] # 判断计数的大小 return 0
❄️ 2️⃣. C# ❄️
思路1
public class Solution { public int MajorityElement(int[] nums) { int n = nums.Length; // 数组长度 if (n==1) return nums[0]; // 特殊情况 Array.Sort(nums); // 数组排序 int m = 1; // 创建一个变量记录同一元素出现的次数 for (int i=0;i<n-1;i++) // 遍历数组 { if (nums[i]!=nums[i+1]) // 判断是否同一元素 { if (m>n/2) return nums[i+1]; // 判断计数的大小 m=1; }else if(nums[i]==nums[i+1]) // 判断是否同一元素 { m++; if (m>n/2) return nums[i]; // 判断计数的大小 } } return 1; } }
思路2
public class Solution { public int MajorityElement(int[] nums) { Dictionary<int, int> dir = new Dictionary<int, int>(); // 先创建一个哈希表 int n = nums.Length; // 数组长度 if (n == 1) return nums[0]; // 如果长度为1，返回元素 for (int i = 0; i < n; i++) // 遍历数组 { if (dir.ContainsKey(nums[i])) // 如果元素在还行表的key里面，就让 { dir[nums[i]]++; // 对应的值+1 if (dir[nums[i]] > n / 2) return nums[i]; // 判断与n/2的大小，如果大，返回该元素 } else dir[nums[i]] = 1; // 如果不在，初始化计数为1 } return 0; } }
🌔 结语 🌔
坚持最重要，每日一题必不可少！😸
期待你的关注和督促！😛
