169. 多数元素【LeetCode 刷题日记】

记录自己从零开始刷 LeetCode，提高自己的数据结构与算法能力，为了获得更好的工作机会

数组 简单

题目：169. 多数元素
地址：https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

解题情况

• 题目基本是读懂了的，但是实际操作写代码，发现思路其实不太清晰
• 我本来打算用暴力解法，双重 for 循环，然后比较出现的次数，出现最大的次数一定是多数元素，但是我没有找到好的方式来处理 次数++ 的问题

参考优秀题解

• 解法：排序后取中位数
• 时间复杂度：O(n log n)。主要的时间复杂度来自于对数组进行排序，而快速排序算法的时间复杂度平均为 O(n log n)
• 空间复杂度：O(log n)。空间复杂度由排序算法的实现决定，通常为 O(log n)

var majorityElement = function (nums) {
  nums.sort((a, b) => a - b);
  return nums[Math.floor(nums.length / 2)];
};

复盘

• 我看了官方解答后，居然有 5 个解答方式，我一个都没想到，而且里面用哈希表和投票的方式完全是超出我认知范围的，其中有几个方案我感觉太复杂了，自己暂时不是很明白，我就先不看了，我先用其中的排序去中值方式先解题，后续再研究其他方式
• 我其中想的一个方案 for 循环然后比较出现次数，其实和哈希表获取出现次数有一点类似，但是自己代码写的不正确，无法计算出来