文章目录
算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！
大家好，我是布小禅，一个尽力让无情的代码变得生动有趣的IT小白，很高兴能偶认识你，关注我，每天坚持学点东西，我们以后就是大佬啦！
📢 ：
❤布小禅❤ 📢 作者专栏： ❤Python❤ ❤Java❤ ❤力扣题❤ 这是我刷第 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
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 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;
}
} 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;
}
} 坚持最重要，每日一题必不可少！😸
期待你的关注和督促！😛
